just_do_it
BAN USERimport java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class ExistsSubarraySum {
public static void main(String[] args){
int[] testcase1 = {6,5,3,2,1,7};
boolean actual = existsSubarraySum(testcase1, 8);
System.out.println("test1 : target 8 " + actual);
actual = existsSubarraySum(testcase1, 10);
System.out.println("test1 : target 10 " + actual);
int[] testcase2 = {-6,2,3,-2,4,1,-5,6};
actual = existsSubarraySum(testcase2, 7);
System.out.println("test2 : target 7 " + actual);
}
public static boolean existsSubarraySum(int[] a, int target){
// if all elements are non negative, use specialized solution, O(n) time
boolean allElementsAreNonNegative = true;
for (int e : a){
if (e < 0) {
allElementsAreNonNegative = false;
break;
}
}
if (allElementsAreNonNegative) {
return existsSubarraySumNonNegativeElements(a,target);
} else {
// else -- has negative elements
return existsSubarraySumGeneric(a,target);
}
}
public static boolean existsSubarraySumNonNegativeElements(int[] a, int target){
int n = a.length;
int start = 0, sum = 0;
for (int i = 0; i < n; i++){
sum = sum + a[i];
if (sum == target) {
return true;
} else if (sum > target) {
while (sum > target) {
sum = sum - a[start];
start++;
}
}
}
return false;
}
/**
* 1) Compute prefix sums S
* 2) for each i check if S(i) + target present
*/
public static boolean existsSubarraySumGeneric(int[] a, int target){
int n = a.length;
int[] prefixSum = new int[n];
Map<Integer, Set<Integer>> sumVsPrefixIndex = new HashMap<Integer, Set<Integer>>();
for (int i = 0; i < n; i++){
prefixSum[i] = ((i > 0) ? prefixSum[i-1] : 0) + a[i];
Set<Integer> values = (sumVsPrefixIndex.containsKey(prefixSum[i])) ?
sumVsPrefixIndex.get(prefixSum[i]) : new HashSet<Integer>();
values.add(i);
sumVsPrefixIndex.put(prefixSum[i], values);
}
for (int i = 0; i < n; i++){
if (sumVsPrefixIndex.containsKey(prefixSum[i] + target)){
return true;
}
Set<Integer> values = sumVsPrefixIndex.get(prefixSum[i]);
values.remove(i);
if (values.size() == 0){
sumVsPrefixIndex.remove(prefixSum[i]);
}
}
return false;
}
}
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class OptimumScheduler {
public static void main(String[] args){
int testcase[] = {1,1,2,1,2};
int cooldown = 2;
List<Integer> schedule = scheduleMinimizeclockTime(testcase, cooldown);
System.out.println("schedule " + schedule);
}
/**
* Assumptions:
* 1) tasks need to be executed in order
* 2) cooldown is non negative
*/
public static List<Integer> scheduleMinimizeclockTime(int[] tasks, int cooldown) {
Map<Integer,Integer> earliestEligibleStartTime = new HashMap<Integer, Integer>();
int t = 0;
List<Integer> schedule = new LinkedList<Integer>();
for (int task : tasks){
if (earliestEligibleStartTime.containsKey(task)){
int treq = earliestEligibleStartTime.get(task);
while (t < treq) {
schedule.add(-1);
t++;
}
}
schedule.add(task);
earliestEligibleStartTime.put(task, t + cooldown + 1);
t++;
}
return schedule;
}
}
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class PathFinderUseDFS {
class Cell {
short x,y;
public Cell(short x, short y){
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof Cell)) {
return false;
}
Cell c = (Cell) o;
return (x == c.x) && (y == c.y);
}
@Override
public int hashCode() {
return (new Short(x)).hashCode() + (new Short(y)).hashCode();
}
}
public static void main(String[] args){
short[][] testcase = {
{1,1,0,1},
{0,1,1,1},
{0,1,0,1},
{1,1,1,1}
};
// for DFS using recursive function leads to cleaner code
// vs handling the recursion stack during the interview
PathFinderUseDFS evaluator = new PathFinderUseDFS(testcase);
evaluator.findAndPrintShortestPath((short) 0, (short) 0, (short) 0, (short) 3);
}
short[][] grid;
int n,m;
List<Cell> shortestPath;
public PathFinderUseDFS(short[][] grid){
this.grid = grid;
n = grid.length;
m = grid.length;
}
public void findAndPrintShortestPath(
short startX, short startY,
short endX, short endY) {
// check start, end in grid
// check if start and end are valid cells
int maxDistance = n*m;
int distance[][] = new int[n][m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++) {
distance[i][j] = maxDistance;
}
}
List<Cell> currentPath = new LinkedList<Cell>();
Set<Cell> nodesInCurrentPath = new HashSet<Cell>();
Cell start = new Cell(startX, startY);
currentPath.add(start);
nodesInCurrentPath.add(start);
shortestPath = new LinkedList<Cell>();
findShortestPath(endX, endY,
start, currentPath, nodesInCurrentPath, distance);
// print shortest path
System.out.print("shortest path ");
for (Cell cell : shortestPath) {
System.out.print("(" + cell.x + "," + cell.y + ") ");
}
System.out.println();
}
public void findShortestPath(
short endX, short endY,
Cell cell, List<Cell> currentPath, Set<Cell> nodesInCurrentPath,
int[][] distance) {
// base cases
if (grid[cell.x][cell.y] == 0) {
return;
}
// check distance
// if smaller add neighbors
int currentPathLength = currentPath.size() - 1;
if (currentPathLength < distance[cell.x][cell.y]){
distance[cell.x][cell.y] = currentPathLength;
// base case
if ((cell.x == endX) && (cell.y == endY)) {
// update overall shortest path
shortestPath = new LinkedList<Cell>(currentPath);
return ;
}
List<Cell> neighbors = new LinkedList<Cell>();
if (cell.x - 1 >= 0) {
neighbors.add(new Cell((short)(cell.x-1), cell.y));
}
if (cell.x + 1 < n) {
neighbors.add(new Cell((short)(cell.x+1), cell.y));
}
if (cell.y - 1 >= 0) {
neighbors.add(new Cell(cell.x, (short)(cell.y-1)));
}
if (cell.y + 1 < m) {
neighbors.add(new Cell(cell.x, (short)(cell.y+1)));
}
for (Cell neighbor : neighbors) {
if (!nodesInCurrentPath.contains(neighbor)){
// update current path
currentPath.add(neighbor);
nodesInCurrentPath.add(neighbor);
findShortestPath(endX, endY,
neighbor, currentPath, nodesInCurrentPath, distance);
// undo changes to current path
currentPath.remove(neighbor);
nodesInCurrentPath.remove(neighbor);
}
}
}
}
}
1) Brute force solution : for look for all pairs (si, sj) with (i < j) check if (si concat sj) is a palindrome. Complexity O(n^2 l) where l is max length of input strings
2)
a) Construct trie over all input strings (mark leaves as regular)
b) All all input strings reverse and add to trie (mark these leaves as reversed)
c) For each node on trie, count number of leaves of type reversed that can be reached via paths that are palindromes , say c(node) is this count
d) Sum c(node) where node is a regular leaf
Complexity O(nl) , but very difficult to prove complexity and get working code in 45 minutes
public class TraverseGridGivenACell {
class Space {
String occupant;
// assume four neighbors, always in order up , down, left, right
// some neighbors can be null if cell is on edge / is corner
Space[] neighbors;
}
static short UP = 0;
static short DOWN = 1;
static short LEFT = 2;
static short RIGHT = 3;
static String TREE = "tree";
static String HOUSE = "house";
static String EMPTY = "";
/**
* 1) get to a known corner , using top left corner
* 2) traverse grid and count
* start at beginning of row and go right
* move down to next row
*/
public int traverseAndCountCellsOfType(Space startCell, String type) {
if (type == null || type != TREE || type != HOUSE || type != EMPTY){
return 0;
}
if (startCell == null) { return 0; }
// get to a known corner , using top left corner
Space origin = startCell;
while (origin.neighbors[LEFT] != null){
origin = origin.neighbors[LEFT];
}
while (origin.neighbors[UP] != null){
origin = origin.neighbors[UP];
}
// traverse grid and count
int res = 0;
Space rowStartCell = origin;
while (rowStartCell != null) {
Space cell = rowStartCell;
while (cell != null){
if(type.equals(cell.occupant)) {res++;}
cell = cell.neighbors[RIGHT];
}
rowStartCell = rowStartCell.neighbors[DOWN];
}
return res;
}
}
import java.util.HashMap;
import java.util.Map;
public class CheckDictionarySorted {
public static void main(String[] args){
String words[] = {"cc", "cb", "b", "bb", "ac"};
char ordering[] = {'c', 'b', 'a' };
boolean actual = isSorted(words, ordering);
System.out.println("testcase1 result " + actual);
words = new String[] {"cc", "cb", "bb", "ac"};
ordering = new char[] {'b', 'c', 'a' };
actual = isSorted(words, ordering);
System.out.println("testcase2 result " + actual);
}
/**
* rely on transitive property of less than
* subproblem: check s(i) < s(i+1)
*
* Assumptions :
* 1) no duplicates in words , ordering
* 2) ordering contains needed alphabets from words
*/
public static boolean isSorted(String[] words, char[] ordering) {
int n = words.length;
if (n < 2) { return true;}
Map<Character, Integer> charToOrdinal = new HashMap<Character, Integer>();
for (int i = 0; i < ordering.length; i++){
charToOrdinal.put(ordering[i], i);
}
char[] prev = words[0].toCharArray();
for (int i = 1; i < n; i++){
char[] current = words[i].toCharArray();
// s1 : prev, s2 : current
char[] s1 = prev, s2 = current;
int s1n = prev.length;
int s2n = current.length;
int j1 = 0, j2 = 0;
boolean smaller = false;
while ((j1 < s1n) && (j2 < s2n)) {
int o1 = charToOrdinal.get(s1[j1]);
int o2 = charToOrdinal.get(s2[j2]);
if (o1 > o2) {
return false;
} else if (o1 < o2) {
smaller = true;
break;
}
j1++; j2++;
}
if (!smaller) {
// substrings identical, enforce 'b' < 'bc'
if (s1n > s2n){
return false;
}
}
prev = current;
}
return true;
}
}
public class MovingAverageWithCircularLinkedList {
class Link {
int data;
public Link next = null;
public Link(int data) {
this.data = data;
}
}
int numElements = 0;
int sum = 0;
int N;
Link current = null;
public MovingAverageWithCircularLinkedList(int N){
this.N = N;
}
public static void main(String[] args){
int testcase[] = new int[] {-1, 5, 4, -3, 0, 7, 2};
MovingAverageWithCircularLinkedList streamaggregator = new MovingAverageWithCircularLinkedList(3);
for (int v : testcase) {
double avg = streamaggregator.update(v);
System.out.println("" + v + " avg: " + avg);
}
}
/**
* update and return running average
* approach does not pad at the beginning , rather returns sum(0..l-1)/l when l < N
*/
public double update(int e) {
if (numElements < N) {
Link l = new Link(e);
if (numElements == 0){
l.next = l;
} else {
l.next = current.next;
current.next = l;
}
current = l;
sum += e;
numElements++;
} else {
current = current.next;
sum = sum + e - current.data;
current.data = e;
}
return ((double) sum )/ numElements;
}
}
this looks to be continuation of question?id=5757912092770304
- just_do_it November 11, 2018import java.util.Arrays;
public class MoveNonZeroElementsToEndOfArray {
public static void main(String[] args){
int test1[] = new int[] {1,0,-2,0,3};
int test2[] = new int[] {0,0};
int test3[] = new int[] {1,2,3};
System.out.println(Arrays.toString(test1));
compactify(test1);
System.out.println(Arrays.toString(test1));
System.out.println(Arrays.toString(test2));
compactify(test2);
System.out.println(Arrays.toString(test2));
System.out.println(Arrays.toString(test3));
compactify(test3);
System.out.println(Arrays.toString(test3));
}
public static int compactify(int[] inp) {
int n = inp.length;
int destIndex = -1;
for (int i = n-1; i >= 0; i--) {
if ((destIndex > 0) && (inp[i] != 0)){
// swap inp[i] and inp[destIndex]
int tmp = inp[i];
inp[i] = inp[destIndex];
inp[destIndex] = tmp;
destIndex--;
} else if ((destIndex < 0) && (inp[i] == 0)) {
destIndex = i;
}
}
System.out.println("#non zero " + (n-(destIndex+1)));
return destIndex+1;
}
}
import java.util.HashMap;
import java.util.Map;
public class EnumeratePatterns {
public static void main(String[] args){
// testcase
Map<String, char[]> dict = new HashMap<String, char[]>();
dict.put("1", new char[] {'A', 'B', 'C'});
dict.put("2", new char[] {'D', 'E'});
dict.put("12", new char[] {'X'});
dict.put("3", new char[] {'P', 'Q'});
enumerate("123", dict);
}
public static void enumerate(String inp, Map<String,char[]> dict) {
enumerate(inp.toCharArray(), "", 0, inp.length(), dict);
}
public static void enumerate(char[] inp, String prefix, int begin, int n, Map<String,char[]> dict) {
// base case
if (begin == n){
System.out.println(prefix);
}
// extend prefix
String key = "";
for (int i = begin; i < n; i++){
if(dict.containsKey(key + inp[i])){
key = key + inp[i];
char[] values = dict.get(key);
for (char c : values){
String extendedPrefix = prefix + c;
enumerate(inp, extendedPrefix, i+1, n, dict);
}
}
}
}
}
import java.util.Arrays;
import java.util.Stack;
public class MinDeletionsToBalanceParantheses {
public static void main(String[] args){
String[] testcase = { "()())()" , "((a((aa((()d(())(",
"())))()(((()))))))()(((()(()))("
};
for (String test : testcase){
String res = balance(test);
System.out.println(test + " result: " + res);
}
}
public static String balance(String inp) {
Stack<Integer> stack = new Stack<Integer>();
int n = inp.length();
char[] inpc = inp.toCharArray();
boolean[] markedForDeletion = new boolean[n];
Arrays.fill(markedForDeletion, false);
for (int i = 0; i < n; i++) {
char c = inpc[i];
if (c == ')') {
if (stack.isEmpty()) {
markedForDeletion[i] = true;
} else {
stack.pop();
}
} else if(c == '('){
stack.push(i);
}
}
while(!stack.isEmpty()){
markedForDeletion[stack.pop()] = true;
}
int numDeletions = 0;
String res = "";
for (int i = 0; i < n; i++){
if (!markedForDeletion[i]){
res = res + inpc[i];
} else {
numDeletions++;
}
}
System.out.println("numDeletions " + numDeletions);
return res;
}
}
package practice2018;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class NextPermutation {
public static void main(String[] args){
String[][] testcases = {
{"12", "21"},
{"315","351"},
{"583","835"},
{"12389","12398"},
{"34722641","34724126"}
};
for(int i = 0; i < testcases.length; i++){
try {
String actual = next(testcases[i][0]);
System.out.println("test " + testcases[i][0] + " actual " + testcases[i][1] + " " + actual);
} catch (Exception e){
System.out.println("test " + testcases[i][0] + " " + e.getMessage());
}
}
}
public static String next(String inp) throws Exception {
char[] digits = inp.toCharArray();
int n = digits.length;
for (int i = n-1; i> 0; i--){
if(digits[i-1] < digits[i]){
// find immediate next permutation for substring(digits,i-1)
List<Character> a = new ArrayList<Character>();
for (int j = i-1; j < n; j++){
a.add(digits[j]);
}
Collections.sort(a);
// find smallest digit larger than digits[i-1] in digits[i, ..]
String partial = "";
for (int j = 0; j < a.size(); j++){
if (a.get(j) > digits[i-1]){
partial += a.get(j);
for (int k = 0; k < a.size(); k++){
if (k != j){
partial += a.get(k);
}
}
break;
}
}
String result = "";
for (int j = 0; j < i-1; j++){
result += digits[j];
}
result += partial;
return result;
}
}
throw new Exception("At maximum, cannt find next");
}
}
public class ShortestStringContainingKeywords {
public static void main(String[] args){
String[][] testcases = {
{"sky", "cloud", "google", "search", "sky", "work", "blue"},
{"sky", "blue"},
{"sky", "cloud", "google", "search", "sky", "work", "blue", "sky"},
{"sky", "blue"}};
for(int i = 0; i < testcases.length/2; i++){
String doc[] = testcases[2*i];
String keywords[] = testcases[2*i+1];
String res = search(doc, keywords);
System.out.println(Arrays.toString(doc) + "\t" + res);
}
}
/**
* keep track of list of occurrences of word,
* -- if all words covered have a feasible solution
* -- if word occurring second time, move forward iterators
* until there is a word that is covered only once
*/
private static String search(String[] doc, String[] keywords) {
Map<String, Integer> keywordId = new HashMap<String, Integer>();
int numKeywords = 0;
for(String kw : keywords){
keywordId.put(kw, numKeywords);
numKeywords++;
}
short n = (short) doc.length;
short optWindowStart = 0, currWindowStart = 0;
short optWindowLength = (short) (n + 1);
int[] numMatches = new int[numKeywords];
for(int i = 0; i < numKeywords; i++){
numMatches[i] = 0;
}
int numKeywordMatches = 0;
List<Integer> tokenIdToMatchingKw = new ArrayList<Integer>();
for(short i = 0; i < n; i++){
if(keywordId.containsKey(doc[i])){
int kwIndex = keywordId.get(doc[i]);
tokenIdToMatchingKw.add(kwIndex);
if(numMatches[kwIndex] == 0){
numKeywordMatches++;
}
numMatches[kwIndex]++;
if(numKeywordMatches == numKeywords){
short j = currWindowStart;
while(j < i){
int kwj = tokenIdToMatchingKw.get(j);
if(kwj != -1){
if(numMatches[kwj] > 1){
numMatches[kwj]--;
j++;
} else {
// local maximum
currWindowStart = j;
short currWindowLength = (short) (i - j + 1);
if(currWindowLength < optWindowLength){
optWindowLength = currWindowLength;
optWindowStart = currWindowStart;
}
break;
}
}
j++;
}
}
} else {
tokenIdToMatchingKw.add(-1);
}
}
if(optWindowLength > n)
return null;
String res = "";
for (short j = optWindowStart; j < optWindowStart + optWindowLength; j++) {
if(j > 0){
res += " " + doc[j];
} else {
res += doc[j];
}
}
return res;
}
}
package google;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class ReverseWords {
public static void main(String[] args){
String[] testcases = {"Hello World", "Hello flat World"};
for(int i = 0; i < testcases.length; i++){
String s = testcases[i];
char[] res = reverseWords(s, " ");
System.out.println(s + "\t" + Arrays.toString(res));
}
}
static char[] reverseWords(String s, String separators){
if(s == null || separators == null){
return null;
}
char[] sc = s.toCharArray();
if(separators.length() == 0 || s.length() <= 1){
return sc;
}
Set<Character> sep = new HashSet<Character>();
for(char c : separators.toCharArray()){
sep.add(c);
}
reverseWords(sc, sep);
return sc;
}
private static void reverseWords(char[] sc, Set<Character> separators) {
// keep track of indices of prev and current separators
int prevSeparator = -1, nextSeparator = -1;
int n = sc.length;
for(int i = 0; i < n; i++){
char c = sc[i];
if(separators.contains(c)){
int tmp = nextSeparator;
nextSeparator = i;
prevSeparator = tmp;
// optional optimization
if(nextSeparator > prevSeparator+2){
// reverse portion between prev+1 and next-1
int wordSize = nextSeparator - (prevSeparator+1);
reverseSubArray(sc, prevSeparator+1, wordSize);
}
}
}
if(nextSeparator != n-1){
int wordSize = n-1 - (nextSeparator+1) + 1;
reverseSubArray(sc, nextSeparator+1, wordSize);
}
}
static void reverseSubArray(char[] sc, int wordStart, int wordSize){
int j = 0;
while(j < wordSize-1-j){
char tmpc = sc[wordStart+j];
sc[wordStart+j] = sc[wordStart+wordSize-1-j];
sc[wordStart+wordSize-1-j] = tmpc;
j++;
}
}
}
package nvidia;
import java.util.Arrays;
// import org.junit.Assert;
public class CheckAnagrams {
public static void main(String[] args){
String[][] testcases = { {"anagram", "granmaa" }};
for(int i = 0; i < testcases.length; i++){
String s1 = testcases[i][0];
String s2 = testcases[i][1];
boolean res = areAnagrams(s1, s2);
System.out.println(s1 + "\t" + s2 + "\t" + res);
}
}
static boolean areAnagrams(String s1, String s2) {
if(s1 == null && s2 == null){
return true;
} else if (s1 == null || s2 == null){
return false;
} else if (s1.length() != s2.length()){
return false;
}
int n = s1.length();
char c1[] = s1.toCharArray();
Arrays.sort(c1);
char c2[] = s2.toCharArray();
Arrays.sort(c2);
for(int i = 0; i < n; i++){
if(c1[i] != c2[i]) {
return false;
}
}
return true;
}
}
package nvidia;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
// import org.junit.Assert;
public class LongestConsecutiveSubarray {
static void findAndPrintMaxConsecSubArray(int[] a) {
int n = a.length;
int maxL = 1, maximizerStart = 0;
Set<Integer> s = new HashSet<Integer>();
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(j-i < maxL) {
continue;
}
// find min and max, check if distinct
s.clear();
int min = a[i], max = a[i];
for(int k = i; k < j; k++){
if(s.contains(a[k])) {
break;
} else {
s.add(a[k]);
if(a[k] < min){
min = a[k];
} else if (a[k] > max) {
max = a[k];
}
}
}
int m = j-i;
if((s.size() == m) && (max-min == m-1)) {
maxL = m;
maximizerStart = i;
}
}
}
System.out.println("max length " + maxL);
for(int i = maximizerStart; i < maximizerStart + maxL; i++){
System.out.print(a[i] + "\t");
}
System.out.println();
}
static void findAndPrintMaxConsecSubSeq(int[] a) {
Arrays.sort(a);
int n = a.length;
// 4 , 5 , 10, 11, 31, 32, 33, 34
int maxL = 1, currL = 1, maximizerStart = 0;
for(int i = 0; i < n; i++){
if(i+1 < n && (a[i+1] == a[i] + 1)) {
currL = currL + 1;
if(currL > maxL){
maxL = currL;
maximizerStart = i - currL+2;
}
} else {
currL = 1;
}
}
System.out.println("max length " + maxL);
for(int i = maximizerStart; i < maximizerStart + maxL; i++){
System.out.print(a[i] + "\t");
}
System.out.println();
}
public static int getNOnes(int n)
{
int result = 0;
while(n>0)
{
n = n&(n-1);
result++;
}
return result;
}
public static void main(String[] args){
int[] testcase1 = {4, 5, 34, 33, 32, 11, 10, 31};
int[] testcase2 = {4, 5, 34, 32, 11, 33, 10, 31};
findAndPrintMaxConsecSubSeq(testcase1);
findAndPrintMaxConsecSubSeq(testcase2);
int[] testcase3 = { 4 , 5 , 33, 34, 32, 31, 11, 10};
findAndPrintMaxConsecSubArray(testcase3);
}
}
T(k) = 2T(k-1) + Sum_{1<=i<=k-2} T(i)*T(k-1-i)
- just_do_it May 12, 2015public class TreeDistance {
class Node {
int v;
Node left, right;
public Node(int v){
this.v = v;
left = right = null;
}
}
public TreeDistance() {
}
static List<Node> pathToNode(Node root, Node n){
if(root == null || n == null){
return null;
}
List<Node> result = new LinkedList<Node>();
if(root == n){
result.add(n);
} else {
List<Node> subRes = null;
if(root.left != null){
subRes = pathToNode(root.left, n);
if(subRes != null){
result.add(root);
result.addAll(subRes);
}
}
if(subRes == null && root.right != null){
subRes = pathToNode(root.right, n);
if(subRes != null){
result.add(root);
result.addAll(subRes);
}
}
if(subRes == null){
result = null;
}
}
return result;
}
static int computeTreeDistance(Node root, Node n1, Node n2) throws Exception{
if(root == null || n1 == null || n2 == null){
throw new IllegalArgumentException();
}
List<Node> pathToN1, pathToN2;
pathToN1 = pathToNode(root, n1);
pathToN2 = pathToNode(root, n2);
// one of nodes not present
if(pathToN1 == null || pathToN2 == null){
throw new Exception("One of the nodes not in the tree");
}
int d1 = pathToN1.size(), d2 = pathToN2.size();
int res = d1 + d2;
boolean done = (d1==0 || d2==0) || (pathToN1.get(0) != pathToN2.get(0));
while(!done){
res = res-2;
pathToN1.remove(0);
pathToN2.remove(0);
}
return res;
}
}
Backend:
> take snapshots of graph every 6 hours
> compute friends of friends on this graph using pregel / other custom two hop traversals
>> maintain evidence of distance 2 (say ids of common friends)
> maintain list of edits (friend adds, deletes - rare but happen!) at each end vertex
Webapp:
Case 1: distance 2 in last precomputation
> lookup latest precomputed distance 2 evidence
> see if edits at source / destination invalidate evidence
Case 2: distance 2 due to recent additions
> get friend lists for source and destination
> join on additions
import java.util.PriorityQueue;
public class MaxAreaRectangle {
class HeightAndPosition implements Comparable<HeightAndPosition> {
int height, position;
public HeightAndPosition(int height, int position) {
this.height = height;
this.position = position;
}
@Override
public int compareTo(HeightAndPosition arg0) {
return height - arg0.height;
}
}
public MaxAreaRectangle() {
}
public int evaluate(int[] a){
int n = a.length;
int[] heights = new int[n+1];
for(int i = 0; i < n; i++){
heights[i] = a[i];
}
heights[n] = 0;
PriorityQueue<HeightAndPosition> activeRectangles = new PriorityQueue<HeightAndPosition>();
int maxArea = 0;
for(int i = 0; i < n; i++){
if(activeRectangles.size() > 0 && activeRectangles.peek().height >= heights[i]){
// update all rectangles that get closed now
int minLeftIndex = i;
while(activeRectangles.size() > 0 && activeRectangles.peek().height >= heights[i]){
HeightAndPosition e = activeRectangles.poll();
// close rectangle
int area = (i - e.position)*e.height;
maxArea = Math.max(maxArea, area);
minLeftIndex = Math.min(minLeftIndex, e.position);
}
HeightAndPosition e = new HeightAndPosition(heights[i],minLeftIndex);
activeRectangles.add(e);
} else {
HeightAndPosition e = new HeightAndPosition(heights[i],i);
activeRectangles.add(e);
}
}
return maxArea;
}
public static void main(String[] args){
MaxAreaRectangle wrapper = new MaxAreaRectangle();
int[] testcase = { 7 , 4 , 4 , 2 , 3 };
int c = wrapper.evaluate(testcase);
System.out.println("cost " + c);
}
}
public class MinCostToValidRPN {
public MinCostToValidRPN() {
}
final static char VALUE = 'x';
final static char OPERATOR = '*';
static int evaluate(String s){
if(s == null){
throw new IllegalArgumentException();
}
int n = s.length();
char[] sc = s.toCharArray();
int result = 0;
// base case
if(n == 0){
result = 1;
} else if (n == 1){
if(sc[0] == VALUE){
result = 0;
} else {
result = 1;
}
} else {
int cost[][][] = new int[n][n][3];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cost[i][j][0] = j-i+1;
cost[i][j][1] = j-i+1;
cost[i][j][2] = j-i+1;
}
}
// fill diagonal
for(int i = 0; i < n; i++){
char c = sc[i];
if(c == VALUE){
cost[i][i][0] = 0;
cost[i][i][1] = 1;
cost[i][i][2] = 1;
} else {
cost[i][i][0] = 1;
cost[i][i][1] = 0;
cost[i][i][2] = 1;
}
}
// compose solution for larger span
for(int length = 2; length < n; length++){
for(int i = 0; i < n-length; i++){
helper(sc, cost,i,i+length);
}
}
result = cost[0][n-1][0];
}
return result;
}
/**
* start at i end at j-1
*/
private static void helper(char[] sc, int[][][] cost, int i, int j) {
// base - delete until left with X
boolean containsValue = false;
for(int k = i; k < j; k++){
if(sc[k] == VALUE){
containsValue = true;
break;
}
}
int y = j - i + 1;
if(containsValue){
y = y-1;
}
for(int k = i-1; k<j-1; k++){
for(int l = k+1; l<j; l++){
int c1 = 1;
if(k>=i){
c1 = cost[i][k][0];
}
int c2 = cost[k+1][l][0];
int c3 = 1;
if(l+1 <=j ){
c3 = cost[l+1][j][1];
}
if(c1+c2+c3<y){
y = c1+c2+c3;
}
}
}
boolean containsOp = false;
for(int k = i; k < j; k++){
if(sc[k] == OPERATOR){
containsOp = true;
break;
}
}
int z = j-i+1;
if(containsOp){
z = z-1;
}
cost[i][j][0] = y;
cost[i][j][1] = z;
}
public static void main(String[] args){
MinCostToValidRPN wrapper = new MinCostToValidRPN();
String[] testcase = { "x" , "*" , "xxx**" , "*xx" };
for(String s : testcase){
System.out.println(s);
int c = wrapper.evaluate(s);
System.out.println("cost " + c);
}
}
}
import java.util.HashMap;
import java.util.Map;
public class FindWordCombination {
public FindWordCombination() {
}
public String solve(String[] L, int k, String target){
if(target == null || L == null){
throw new IllegalArgumentException();
}
if(L.length == 0){
return "";
}
Map<String, Integer> dictionary = new HashMap<String,Integer>();
for(String s : L){
int freq = 1;
if(dictionary.containsKey(s)){
freq = dictionary.get(s);
freq = freq + 1;
}
dictionary.put(s,freq);
}
int m = L.length;
int n = target.length();
//char sc[] = target.toCharArray();
int start = -1;
for(int i = 0; i < k; i++){
start = i;
int numMatches = 0;
boolean misMatch = false;
Map<String, Integer> wordFreq = (new HashMap<String,Integer>(dictionary));
while((numMatches < m) && ((start+k) < n)){
String ss = target.substring(start, start+k);
misMatch = !wordFreq.containsKey(ss);
if(!misMatch){
// decrement frequency
int freq = wordFreq.get(ss);
if(freq > 1){
wordFreq.put(ss, freq-1);
} else {
wordFreq.remove(ss);
}
numMatches++;
} else {
if(numMatches > 0){
wordFreq = (new HashMap<String,Integer>(dictionary));
}
}
//System.out.println("DEBUG " + ss + " " + numMatches);
start=start+k;
}
if(numMatches == m){
start = start - k*m;
break;
}
}
if(start < 0){
System.err.println("No solution exists");
return null;
}
String res = target.substring(start, start+k*m);
return res;
}
public static void main(String[] args){
FindWordCombination wrapper = new FindWordCombination();
String L[] = {"fooo", "barr", "wing", "ding", "wing"};
String s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
{
String res = wrapper.solve(L, 4, s);
System.out.println("input:\t" + s);
System.out.println("result:\t" + res);
}
}
}
Hashing is easier to code in an interview and works well in practice. KMP is good to mention to convey to the interviewer that one knows about worst case complexities
- just_do_it March 26, 2015public static String dedupe(String s){
if(s == null || s.length() < 2){
return s;
}
boolean used[] = new boolean[256];
Arrays.fill(used, false);
StringBuffer sb = new StringBuffer();
char[] sc = s.toCharArray();
for(int i = 0; i < sc.length; i++){
if(!used[(short) sc[i]]){
sb.append(sc[i]);
used[(short) sc[i]] = true;
}
}
return sb.toString();
}
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
*
* At each index decide to hold, buy or sell
* maximize profit per unit of stock held
*
*/
public class DayTraderWithPerfectInformation {
static final short BUY = 1;
static final short SELL = -1;
static final short HOLD = 0;
double profit[];
double maxProfit;
public DayTraderWithPerfectInformation() {
maxProfit = 0;
}
// use atmost N trades
public double[] maximize(List<Short> pricesL, short N){
int m = pricesL.size();
Short[] price = pricesL.toArray(new Short[1]);
profit = new double[N];
double profitBeforeLastCycle[] = new double[N];
for(int i = 0; i < N; i++){
profitBeforeLastCycle[i] = 0;
}
double profitBreakdown[][] = new double[N][];
for(int i = 0; i < N; i++){
profitBreakdown[i] = new double[2*(i+1)];
}
double minSinceLastSell[] = new double[N];
for(int i = 0; i < N; i++){
minSinceLastSell[i] = price[0];
}
double maxSinceLastBuy[] = new double[N];
for(int i = 0; i < N; i++){
maxSinceLastBuy[i] = price[0];
}
for(int i = 0; i < N; i++){
profit[i] = 0;
}
for(short i = 1; i < m; i++){
for(short j = 0; j < N; j++){
if(price[i] < minSinceLastSell[j]){
// have a new min can take profit now
// profit from sale before taking new min?
double x = maxSinceLastBuy[j] - minSinceLastSell[j];
x = x + profitBeforeLastCycle[j];
if(x > profit[j]){
profit[j] = x;
profitBreakdown[j][0] = minSinceLastSell[j];
profitBreakdown[j][1] = maxSinceLastBuy[j];
}
minSinceLastSell[j] = price[i];
maxSinceLastBuy[j] = 0;
if(j>0){
profitBeforeLastCycle[j] = profit[j-1];
}
//System.out.println("DEBUG " + x + "\t" + profit[j]);
} else if(price[i] > maxSinceLastBuy[j]){
maxSinceLastBuy[j] = price[i];
}
}
}
for(short j = 0; j < N; j++){
if(maxSinceLastBuy[j] > minSinceLastSell[j]){
double x = maxSinceLastBuy[j] - minSinceLastSell[j];
x = x + profitBeforeLastCycle[j];
if(x > profit[j]){
profit[j] = x;
profitBreakdown[j][0] = minSinceLastSell[j];
profitBreakdown[j][1] = maxSinceLastBuy[j];
}
}
}
maxProfit = profit[0];
for(int i = 0; i < N; i++){
if(maxProfit > profit[i]){
maxProfit = profit[i];
}
}
return profit;
}
public static void main(String[] args){
DayTraderWithPerfectInformation wrapper = new DayTraderWithPerfectInformation();
short a[] = {86, 98, 92, 68, 67, 56, 52, 96};
List<Short> testcase = new LinkedList<Short>();
for(int i = 0; i < 8; i++){
//testcase.add( (short) (Math.random()*50 + 50));
testcase.add(a[i]);
}
//double[] res = wrapper.maximize(testcase, (short) 1);
double[] res = wrapper.maximize(testcase, (short) 2);
System.out.println("quotes:\t" + Arrays.toString(testcase.toArray(new Short[1])));
System.out.println("MAX PROFIT " + wrapper.maxProfit);
System.out.println("DEBUG " + Arrays.toString(res));
}
}
by look for I meant "solve for smallest subsequence of numbers forming atleast"
- just_do_it March 14, 2015here are my thoughts for smallest subsequence with sum exceeding k
find the median, and sum all elements greater than median,
> if sum < k, look for k-sum in second half
> else prune second half, look for k in first half
this question can take up the entire interview, for instance how to model retweets, authority of people tweeting / retweeting, what about topics not mentioned in tweet and can be inferred from it
- just_do_it March 14, 2015public class SelectionOnBST {
class Node {
int v;
Node left, right;
public Node(int v){
this.v = v;
left = right = null;
}
}
static class Pair {
Node n;
int x;
public Pair(Node n, int x){
this.n = n;
this.x = x;
}
}
public SelectionOnBST() {
}
/**
* Assume read only nodes, cannot store heights
*/
static Node findKthLargestElement(Node root, int k){
Pair p = helper(root, k);
if( p == null){
return null;
} else {
return p.n;
}
}
static Pair helper(Node root, int k){
int numExamined = 0;
if(root == null || k <=0){
return new Pair(null,0);
} else if(root.right == null && root.left == null){
numExamined = 1;
if(k == 1){
// found
return new Pair(root, k);
} else {
return new Pair(null, 1);
}
} else if(root.right != null){
Pair p = helper(root.right,k);
numExamined = p.x;
if(numExamined == k){
// found
return p;
}
}
if(numExamined == (k-1)){
// found
return new Pair(root,k);
} else {
numExamined++;
}
if(root.left != null){
Pair p = helper(root.left, k-numExamined);
// found
if(p.n != null){
p.x = k;
return p;
} else {
numExamined += p.x;
}
}
return new Pair(null,numExamined);
}
}
KMP is optimal worst case complexity, hashing is very practical and easy to code, I would start with that.
m = needle.length();
hash function f would be for the form
f(c1c2...cm) = (c1x^(m-1) + c2x^(m-2) + ... + cm) % D where x and D are primes
// precompute x^j for j < m
f(i+1:m+i) = (f(i:m+i-1) - cix^(m-1))*x + c(m+i)
I can pass a moving window on haystack and compute hash(i:i+m-1) efficiently,
use that to filter out mismatches and fallback on character by character comparison when hash values match
Look at entropy of needle and decide on number of hash functions to use, more hash functions if needle has low entropy
// 25 and 1009 are relatively prime
public class StringCounterV2 {
static final int MAX_LENGTH = 101;
static final int MOD = 1009;
static long simpleCounts[] = new long[MAX_LENGTH];
static {
long x = 1;
for(int i = 0; i < MAX_LENGTH; i++){
simpleCounts[i] = x;
x = (x*25) % 1009;
}
}
public StringCounterV2() {
}
long count(String s){
if(s == null){
throw new IllegalArgumentException("non empty string expected");
}
//System.out.println("DEBUG " + s);
char[] sc = s.toCharArray();
int n = sc.length;
long res;
if(n == 1){
return (sc[0] - 'a'+1) % MOD;
} else if(n == 2){
long res0 = (sc[1] - 'a'+1);
if(sc[1] >= sc[0]){
res0--;
}
long res1 = (sc[0] - 'a')*simpleCounts[1];
res = res0 + res1;
return res % MOD;
}
// to compute count look at count(s1), count(s2), count(s3)
long resk = count(s.substring(1));
long reskMinus1 = count(s.substring(2));
res = (sc[0] - 'a')*simpleCounts[n-1];
if(sc[0] == sc[1]){
if(sc[1] == 'a'){
res = 0;
} else {
res = res + ((sc[1] - 'a')*simpleCounts[n-2]);
}
} else if (sc[0] < sc[1]){
res = res + (resk - simpleCounts[n-2]);
} else {
res = res + resk;
}
//System.out.println("DEBUG " + s + "\t" + res);
return res % 1009;
}
public static void main(String[] args){
String testcase[] = { "bcd" , "bad", "bbd", "caf", "ddd" };
for(String s : testcase){
StringCounterV2 wrapper = new StringCounterV2();
long count = wrapper.count(s);
System.out.println(s + "\t" + count);
}
}
}
There is a recurrence relation for f of the form
f(m,n) = 2n // if m is even
else f(m,n) = 2n + f(n-2,m)
// base cases
f(1,n) = n, f(m,1) = m
eg) f(7,4) = 14 + f(2,7)
= 14 + 4 = 18
assume binary representation of n is of the form
ak ones b(k-1) zeros .... a3 ones b2 zeros a2 ones b1 zeros a1 ones
where ai>0 and bj > 0 (if no zeros at all P2 win)
#swaps to more all ones to least significant positions while staying beautiful would be
s = a2*b1 + a3*(b1+b2) + ... ak*(b1+b2+...b(k-1))
if(s is even) P2 win
else P1 win
Can be done with a variation on dfs, keep track of number of zeroValuedNodes along path from root on a stack, if at a leaf that has non zero value swap with head of stack
If zeroValuedNodes not empty at the end, there is no solution
Outline would be:
sinkZero(Node r){
init stack zeroValuedNodes
dfs(r, zeroValuedNodes)
if stack not empty problem not solvable
}
dfs(Node n, zeroValuedNodes){
if leaf {
if non zero, swap value with head of stack, pop zeroValuedNodes
return
} else {
if zero push onto zeroValuedNodes
if leftChild exists, dfs(left,..)
if rightChild exists, dfs(right,..)
}
return
}
import java.util.LinkedList;
import java.util.List;
public class BoggleVariant {
char[][] c;
int n;
boolean visited[][];
public BoggleVariant(char[][] c, int n){
this.c = c;
this.n = n;
visited = new boolean[n][n];
}
void resetVisits(){
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
visited[i][j] = false;
}
/**
* use backtracking
* @param probe
* @return
*/
boolean containsString(String probe){
char[] probeC = probe.toCharArray();
boolean found = false;
// string can start anywhere
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
resetVisits();
found = containsString(probeC, i, j , 0);
if(found){
return true;
}
}
}
return found;
}
/**
* assume k < probeC.length
* also start location !visited
*/
boolean containsString(char[] probeC , int loci , int locj , int k){
if(k >= probeC.length){
return true;
}
//System.out.println("DEBUG " + k + " (" + loci + "," + locj + ") "+ c[loci][locj] + " " + probeC[k]);
boolean solvable = false;
if(c[loci][locj] == probeC[k]){
visited[loci][locj] = true;
// pre
List<List<Integer>> next = new LinkedList<List<Integer>>();
// valid moves (i,j) -> (i+-1,j+-1)
if(loci+1<n && !visited[loci+1][locj]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci+1); pos.add(locj);
next.add(pos);
}
if(loci-1>=0 && !visited[loci-1][locj]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci-1); pos.add(locj);
next.add(pos);
}
if(locj+1 < n && !visited[loci][locj+1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci); pos.add(locj+1);
next.add(pos);
}
if(locj-1 >= 0 && !visited[loci][locj-1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci); pos.add(locj-1);
next.add(pos);
}
if(loci+1<n && locj+1 < n && !visited[loci+1][locj+1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci+1); pos.add(locj+1);
next.add(pos);
}
if(loci+1<n && locj-1 >=0 && !visited[loci+1][locj-1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci+1); pos.add(locj-1);
next.add(pos);
}
if(loci-1>=0 && locj+1 < n && !visited[loci-1][locj+1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci-1); pos.add(locj+1);
next.add(pos);
}
if(loci-1>=0 && locj-1 >=0 && !visited[loci-1][locj-1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci-1); pos.add(locj-1);
next.add(pos);
}
//System.out.println("remaining " + (probeC.length-1-k));
// base
if(k == (probeC.length-1)){
return true;
}
if(next.size() == 0){
return false;
}
// DFS
for(List<Integer> neighbor : next){
boolean canExtend = containsString(probeC, neighbor.get(0), neighbor.get(1) , k+1);
solvable |= canExtend;
//System.out.println("canExtend (" + loci + "," + locj + ")? " + canExtend);
if(solvable){
return true;
} else {
visited[neighbor.get(0)][neighbor.get(1)] = false;
}
}
} else {
return false;
}
return solvable;
}
public static void main(String[] args){
char[][] testcase = { { 'd' , 'e' , 't' , 'e' },
{ 'i', 'm', 'e', 'r' },
{ 'n' , 'b' , 'r' , 'n' },
{ 'a' , 't' , 'i' , 'o' }
};
BoggleVariant wrapper = new BoggleVariant(testcase, 4);
String probe = "determination";
boolean res = wrapper.containsString(probe);
for(int i = 0; i < 4; i++)
System.out.println(new String(testcase[i]));
System.out.println("\t" + probe + "\t" + res);
}
}
O(n^3) time and O(n) space
- just_do_it February 22, 2015// took 27 minutes
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class MartialArtsStaff {
public MartialArtsStaff() {
}
/**
* result: leftStart, rightStart, L
*/
public List<Integer> getCutsWithMaxBalancedStaff(int[] a){
List<Integer> res = new LinkedList<Integer>();
int maxLength = 0;
if(a != null){
int n = a.length;
int leftStart = -1, rightStart = -1;
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
int wl = 0, wr = 0;
double coml = 0, comr = 0;
int limit = j-i;
if(j+limit >= n){
limit = n-j;
}
for(int l = 0; l < limit; l++){
wl += a[i+l];
wr += a[j+l];
coml += a[i+l]*(l+1);
comr += a[j+l]*(l+1);
if(l+1 > maxLength){
if(wl == wr){
//System.out.println("DEBUG " + i + " " + j + " " + l + " " + wl);
if(coml == comr || coml == (wl*(l+1) - comr)){
maxLength = l+1;
leftStart = i;
rightStart = j;
}
}
}
}
}
}
res.add(leftStart);
res.add(rightStart);
res.add(maxLength);
}
if(maxLength == 0){
res.add(0); res.add(0); res.add(0);
}
return res;
}
public static void main(String[] args){
MartialArtsStaff wrapper = new MartialArtsStaff();
int[] testcase = {1,3,1,2,5,1,1,4,1,2,3,1};
List<Integer> res = wrapper.getCutsWithMaxBalancedStaff(testcase);
System.out.println(Arrays.toString(testcase));
System.out.println(res.get(0) + " " + res.get(1) + " " + res.get(2));
}
}
Here is the outline I can come up with, start with atleast n/3 samples and get new sample triplet if cannot fit yet
1) If the character c appears k times and k>=3, p(ccc) = kC3/nC3, else if there are only triplets with 2 c's k = 2, else k=1
2) If k = 1, and position of c is m then p(c**) = (n-m)C2/nC3
3) If c repeats say at positions m1, m2 , ... mk, p(c**) = Sum from 1 to k of (n-ml)C2/nC3
4) Determine positions of characters with lowest k first and reduce the problem to a smaller size by dropping all triplets containing them
Looking at pair constraints like say c1 appears at i1<i2,...ik and c2 appears at j1<j2<...jl on p(c1c2*) would reduce #samples needed
Not sure what the expectation is for this question, watching for additional solutions
import java.util.LinkedList;
import java.util.List;
public class MaxFluctuationsInTournament {
int[] a;
int s1,s2;
int[][] b;
public MaxFluctuationsInTournament(int[] a, int s1, int s2) {
this.a = a;
this.s1 = s1;
this.s2 = s2;
}
/**
* assume scores non negative, assume only one team scores in a game
* assume a sorted
*/
public int getMaxFlips(){
if(s1<0 || s2 < 0 || (s1==0 && s2==0) || a==null || a.length == 0){
return 0;
}
int k = a.length;
int m = Math.max(a[k-1], s1)+1;
int n = Math.max(a[k-1], s2)+1;
b = new int[m][n];
// base cases
for(int i = 0; i < k; i++){
b[0][a[i]] = 1;
b[a[i]][0] = 1;
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int max = b[i][j];
for(int l = 0; l < k; l++){
int c = 0;
if(a[l] > 0 && a[l] <= i){
c = b[i-a[l]][j];
boolean winnerFlipped = ((i>j)&&(i-a[l]<j));
if(winnerFlipped){
c = c+1;
}
}
if(c > max){
max = c;
}
if(a[l] > 0 && a[l] <= j){
c = b[i][j-a[l]];
boolean winnerFlipped = ((i<j)&&(i>j-a[l]));
if(winnerFlipped){
c = c+1;
}
}
if(c > max){
max = c;
}
}
b[i][j] = max;
}
}
// find maximizer
System.out.println("DEBUG max(#flips)=" + (b[s1][s2]-1));
return b[s1][s2]-1;
}
public List<List<Integer>> getMaximizer(){
int k = a.length;
return findMaximizer(a,k,s1,s2,b);
}
List<List<Integer>> findMaximizer(int[] a, int k, int i, int j, int[][] b){
List<List<Integer>> res = new LinkedList<List<Integer>>();
if(b[i][j] > 0){
List<Integer> prevState = new LinkedList<Integer>();
for(int l = 0; l < k; l++){
int c = 0;
if(a[l] > 0 && a[l] <= i){
c = b[i-a[l]][j];
boolean winnerFlipped = ((i>j)&&(i-a[l]<j));
if(winnerFlipped){
c = c+1;
}
}
if(c == b[i][j]){
// found maximizer
prevState.add(i-a[l]);
prevState.add(j);
break;
}
if(a[l] > 0 && a[l] <= j){
c = b[i][j-a[l]];
boolean winnerFlipped = ((i<j)&&(i>j-a[l]));
if(winnerFlipped){
c = c+1;
}
}
if(c == b[i][j]){
// found maximizer
prevState.add(i);
prevState.add(j-a[l]);
break;
}
}
if(prevState.size() > 0){
res = findMaximizer(a,k,prevState.get(0),prevState.get(1),b);
List<Integer> currState = new LinkedList<Integer>();
currState.add(i);
currState.add(j);
res.add(currState);
}
}
return res;
}
public static void main(String[] args) {
int a[] = { 0 , 1 , 2 , 3 };
int s1 = 10, s2 = 6;
MaxFluctuationsInTournament wrapper = new MaxFluctuationsInTournament(a,s1,s2);
int maxFlips = wrapper.getMaxFlips();
List<List<Integer>> res = wrapper.getMaximizer();
int n = res.size();
System.out.println("Result " + maxFlips);
for(int i = 0; i < n; i++){
List<Integer> state = res.get(i);
System.out.println("State " + (i+1) + "\t(" + state.get(0) + "," + state.get(1) + ")");
}
}
}
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class FunctionEvaluator {
int n;
int[] a;
int[][] fD;
public FunctionEvaluator(int n, List<Integer> val) {
this.n = n;
a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = val.get(i);
}
fD = new int[n][2];
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new FileReader(args[0]));
// read elements
String line;
line = in.readLine().trim();
int n = Integer.parseInt(line);
List<Integer> l = new LinkedList<Integer>();
line = in.readLine();
String token[] = line.split(" ");
for (String s : token) {
int x = Integer.parseInt(s);
l.add(x);
}
FunctionEvaluator wrapper = new FunctionEvaluator(n, l);
List<Integer> left = new LinkedList<Integer>();
List<Integer> right = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
line = in.readLine();
token = line.split(" ");
int x1 = Integer.parseInt(token[0]);
int x2 = Integer.parseInt(token[1]);
left.add(x1);
right.add(x2);
}
wrapper.setFunctionData(left, right);
// edits / evaluatiosn
line = in.readLine().trim();
int k = Integer.parseInt(line);
for (int i = 0; i < k; i++) {
line = in.readLine();
token = line.split(" ");
int opType = Integer.parseInt(token[0]);
int x1 = Integer.parseInt(token[1]);
int x2 = Integer.parseInt(token[2]);
if (opType == 1) {
wrapper.setElement(x1, x2);
} else {
int res = wrapper.evaluate(x1, x2);
System.out.println(res);
}
}
}
// using brute force
int evaluate(int begin, int end) {
int res = 0;
for (int i = begin - 1; i < end; i++) {
res += evaluate(i);
}
return res;
}
int evaluate(int fi) {
int res = 0;
for (int j = fD[fi][0]-1; j < fD[fi][1]; j++) {
res += a[j];
}
System.out.println("DEBUG fi=" + fi + "\t(" + fD[fi][0] + "," + fD[fi][1] + ") " + res);
return res;
}
void setElement(int i, int val) {
a[i - 1] = val;
System.out.println("DEBUG " + Arrays.toString(a));
}
private void setFunctionData(List<Integer> left, List<Integer> right) {
for (int i = 0; i < n; i++) {
fD[i][0] = left.get(i);
fD[i][1] = right.get(i);
}
}
}
Looks like a good interview question with scope for extending question to solve for cases where #elements is very large / #evaluations is very large
- just_do_it February 19, 2015import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class RecursionTest {
public RecursionTest() {
}
int[] compute(int n){
int[] res = null;
if(n == 0){
res = new int[1];
res[0] = 1;
}
// recursion
if(n>0){
int[] prevRes = compute(n-1);
List<Integer> resList = new LinkedList<Integer>();
int prevVal = prevRes[0], freq = 1;
for(int i = 1; i < prevRes.length; i++){
int x = prevRes[i];
if(x == prevVal){
freq++;
} else {
resList.add(freq);
resList.add(prevVal);
prevVal = x;
freq = 1;
}
}
resList.add(freq);
resList.add(prevVal);
res = new int[resList.size()];
for(int i = 0; i < resList.size(); i++){
res[i] = resList.get(i);
}
}
return res;
}
public static void main(String[] args){
RecursionTest wrapper = new RecursionTest();
for(int i = 0; i < 7; i++){
int[] res = wrapper.compute(i);
System.out.print(i + "\t");
System.out.println(Arrays.toString(res));
}
}
}
// sort chars in each string, then sort strings and group
// timing 22 minutes
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class GroupAnagrams {
static class HelperWord implements Comparable<HelperWord>{
String s, sWithCharsSorted;
HelperWord(String s){
this.s = s;
char sc[] = s.toCharArray();
Arrays.sort(sc);
sWithCharsSorted = new String(sc);
}
public String toString(){
return (s + "\t" + sWithCharsSorted);
}
@Override
public int compareTo(HelperWord that) {
int res = ((String) sWithCharsSorted).compareTo(that.sWithCharsSorted);
return res;
}
}
public GroupAnagrams() {
}
private Set<Set<String>> groupAnagrams(String[] a){
Set<Set<String>> res = new HashSet<Set<String>>();
if(a==null) {
return res;
} else if (a.length == 1){
Set<String> y = new HashSet<String>();
y.add(a[0]);
res.add(y);
return res;
}
List<HelperWord> wordsWithCharsSorted = new LinkedList<HelperWord>();
for(String s : a){
HelperWord x = new HelperWord(s);
wordsWithCharsSorted.add(x);
}
Collections.sort(wordsWithCharsSorted);
for(HelperWord x : wordsWithCharsSorted){
System.out.print(x + "\t");
}
System.out.println();
// traverse list and group anagrams
HelperWord prev = wordsWithCharsSorted.get(0);
int groupStart = 0;
for(int i = 1; i < wordsWithCharsSorted.size(); i++){
HelperWord x = wordsWithCharsSorted.get(i);
if(prev.compareTo(x) == 0){
} else {
// have a new cluster
Set<String> y = new HashSet<String>();
for(int j = groupStart; j < i; j++){
HelperWord x2 = wordsWithCharsSorted.get(j);
y.add(x2.s);
}
res.add(y);
groupStart = i;
}
prev = x;
}
Set<String> y = new HashSet<String>();
for(int j = groupStart; j < wordsWithCharsSorted.size(); j++){
HelperWord x2 = wordsWithCharsSorted.get(j);
y.add(x2.s);
}
res.add(y);
return res;
}
public static void main(String[] args){
GroupAnagrams wrapper = new GroupAnagrams();
String[] testcase = { "trees" , "car" , "bike" , "steer" , "arc" };
Set<Set<String>> groups = wrapper.groupAnagrams(testcase);
System.out.println(groups.size());
}
}
// brute force 19 minutes
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class FindEnclosingRectangles {
static class Point implements Comparable<Point>{
int x, y;
Point(int x, int y){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point o) {
//System.out.println(x + "," + y + "\t" + o.x + "," + o.y);
if(o.x != x){
return x - o.x;
} else {
return y - o.y;
}
}
}
static class Rectangle{
Point pLL, pUR;
Rectangle(Point pLL, Point pUR){
this.pLL = pLL;
this.pUR = pUR;
}
boolean contains(Point p){
boolean result = p.compareTo(pLL) >= 0 && pUR.compareTo(p) >= 0;
return result;
}
}
List<Rectangle> rectangles;
public FindEnclosingRectangles() {
rectangles = new LinkedList<Rectangle>();
}
private void addRectangle(Rectangle rectangle) {
rectangles.add(rectangle);
}
private List<Rectangle> find(Point point) {
List<Rectangle> res = new LinkedList<Rectangle>();
for(Rectangle r : rectangles){
if(r.contains(point)){
res.add(r);
}
}
return res;
}
public static void main(String[] args){
FindEnclosingRectangles wrapper = new FindEnclosingRectangles();
wrapper.addRectangle(new Rectangle(new Point(0,0), new Point(4,5)));
wrapper.addRectangle(new Rectangle(new Point(1,2), new Point(5,5)));
List<Rectangle> res = wrapper.find(new Point(3,4));
System.out.println(res.size());
res = wrapper.find(new Point(13,4));
System.out.println(res.size());
}
}
// timing 15 minutes
import java.util.Arrays;
public class SortArrayComposedOf123 {
int begin, end;
public SortArrayComposedOf123() {
}
/*
* sorting in place
*/
void sort(int[] a){
if(a == null){
return;
}
int n = a.length;
// stage 1 get all 1 to left side
begin = 0;
end = n-1;
helper(a,1);
int numOnes = begin;
if(begin>0 && a[begin]!=1){
begin--;
}
// stage 2 get all 3's in remaining to right side
begin = numOnes;
end = n-1;
helper(a,2);
}
void helper(int[] a, int pivot){
while(begin < end ){
if(a[begin] == pivot){
begin++;
} else if(a[end] > pivot){
end--;
} else {
// swap
int x = a[begin];
a[begin] = a[end];
a[end] = x;
begin++; end--;
}
}
}
public static void main(String[] args){
int[] testcase = { 1 , 3 , 2 , 1 , 2 , 3};
SortArrayComposedOf123 wrapper = new SortArrayComposedOf123();
System.out.println("BEFORE");
System.out.println(Arrays.toString(testcase));
wrapper.sort(testcase);
System.out.println("AFTER");
System.out.println(Arrays.toString(testcase));
}
}
package facebook;
public class GetAgeDistributionV2 {
public GetAgeDistributionV2() {
}
int[] getAgeDistribution(int[] a){
int n = a.length;
int maxAge = a[n-1];
int[] frequencies = new int[maxAge+1];
for(int i = 0; i <= maxAge; i++ ){
frequencies[i] = 0;
}
int pivot;
int pivotStart = 0;
while(pivotStart < n){
pivot = a[pivotStart];
int pivotEnd = getLastIndexAndUpdateFrequency( a, pivot, pivotStart, n-1, frequencies);
pivotStart = pivotEnd+1;
}
return frequencies;
}
/**
* assume a[start] = pivot
*/
int getLastIndexAndUpdateFrequency(int[] a, int pivot, int start, int end, int[] frequencies){
if(end==start){
frequencies[pivot]++;
return end;
} else if ( end == (start+1)){
if(a[end] == pivot){
frequencies[pivot] += 2;
return end;
} else {
frequencies[pivot]++;
return start;
}
} else {
int mid = (int) Math.floor((start + end+1)/2.0);
//System.out.println(start + " -> " + end + "\t" + mid);
if(a[mid] == pivot){
frequencies[pivot] += (mid - start);
return getLastIndexAndUpdateFrequency( a, pivot, mid, end, frequencies);
} else {
// a[mid] > pivot
return getLastIndexAndUpdateFrequency( a, pivot, start, mid, frequencies);
}
}
}
public static void main(String[] args){
int[] testcase = { 8 , 8 , 8 , 9 , 9 , 11 , 15 , 16, 16, 16 };
GetAgeDistributionV2 wrapper = new GetAgeDistributionV2();
int freq[] = wrapper.getAgeDistribution(testcase);
for(int i = 0; i < freq.length; i++) {
if(freq[i] != 0 ) {
System.out.println(i + "\t" + freq[i]);
}
}
}
}
import java.util.LinkedList;
import java.util.List;
public class BoggleVariant {
char[][] c;
int n;
boolean visited[][];
public BoggleVariant(char[][] c, int n){
this.c = c;
this.n = n;
visited = new boolean[n][n];
}
void resetVisits(){
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
visited[i][j] = false;
}
/**
* use backtracking
* @param probe
* @return
*/
boolean containsString(String probe){
char[] probeC = probe.toCharArray();
boolean found = false;
// string can start anywhere
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
resetVisits();
found = containsString(probeC, i, j , 0);
if(found){
return true;
}
}
}
return found;
}
/**
* assume k < probeC.length
* also start location !visited
*/
boolean containsString(char[] probeC , int loci , int locj , int k){
if(k >= probeC.length){
return true;
}
//System.out.println("DEBUG " + k + " (" + loci + "," + locj + ") "+ c[loci][locj] + " " + probeC[k]);
boolean solvable = false;
if(c[loci][locj] == probeC[k]){
visited[loci][locj] = true;
// pre
List<List<Integer>> next = new LinkedList<List<Integer>>();
// valid moves (i,j) -> (i+-1,j+-1)
if(loci+1<n && !visited[loci+1][locj]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci+1); pos.add(locj);
next.add(pos);
}
if(loci-1>=0 && !visited[loci-1][locj]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci-1); pos.add(locj);
next.add(pos);
}
if(locj+1 < n && !visited[loci][locj+1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci); pos.add(locj+1);
next.add(pos);
}
if(locj-1 >= 0 && !visited[loci][locj-1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci); pos.add(locj-1);
next.add(pos);
}
if(loci+1<n && locj+1 < n && !visited[loci+1][locj+1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci+1); pos.add(locj+1);
next.add(pos);
}
if(loci+1<n && locj-1 >=0 && !visited[loci+1][locj-1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci+1); pos.add(locj-1);
next.add(pos);
}
if(loci-1>=0 && locj+1 < n && !visited[loci-1][locj+1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci-1); pos.add(locj+1);
next.add(pos);
}
if(loci-1>=0 && locj-1 >=0 && !visited[loci-1][locj-1]){
List<Integer> pos = new LinkedList<Integer>();
pos.add(loci-1); pos.add(locj-1);
next.add(pos);
}
//System.out.println("remaining " + (probeC.length-1-k));
// base
if(k == (probeC.length-1)){
return true;
}
if(next.size() == 0){
return false;
}
// DFS
for(List<Integer> neighbor : next){
boolean canExtend = containsString(probeC, neighbor.get(0), neighbor.get(1) , k+1);
solvable |= canExtend;
//System.out.println("canExtend (" + loci + "," + locj + ")? " + canExtend);
if(solvable){
return true;
} else {
visited[neighbor.get(0)][neighbor.get(1)] = false;
}
}
} else {
return false;
}
return solvable;
}
public static void main(String[] args){
char[][] testcase = { { 'd' , 'e' , 't' , 'e' },
{ 'i', 'm', 'e', 'r' },
{ 'n' , 'b' , 'r' , 'n' },
{ 'a' , 't' , 'i' , 'o' }
};
BoggleVariant wrapper = new BoggleVariant(testcase, 4);
String probe = "determination";
boolean res = wrapper.containsString(probe);
for(int i = 0; i < 4; i++)
System.out.println(new String(testcase[i]));
System.out.println("\t" + probe + "\t" + res);
}
}
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class CoverAllCharacters {
String s;
public CoverAllCharacters(String s){
this.s = s;
}
String computeMinCover(char[] goodChar){
if(s==null){
return null;
}
int k = goodChar.length;
char sc[] = s.toCharArray();
Map<Character, List<Integer>> charLocations = new HashMap<Character, List<Integer>>();
for(char c : goodChar){
charLocations.put(c, new LinkedList<Integer>());
}
for(int i = 0; i < sc.length; i++){
char c = sc[i];
charLocations.get(c).add(i);
}
Map<Character, Integer> earliestLocationInSubstring = new HashMap<Character, Integer>();
/*for(char c : goodChar){
earliestLocationInSubstring.put(c, -1);
}*/
int start = 0;
int bestCoverLength = Integer.MAX_VALUE, bestCoverStart=-1;
for(int i = 0; i < sc.length; i++){
char c = sc[i];
if(!earliestLocationInSubstring.containsKey(c)){
earliestLocationInSubstring.put(c, i);
}
if(earliestLocationInSubstring.size() == k){
boolean done = false;
int nextLocationOfChar;
do {
int coverLength = i+1-start;
if(coverLength < bestCoverLength){
bestCoverStart=start;
bestCoverLength=coverLength;
}
char startChar = sc[start];
charLocations.get(startChar).remove(0);
nextLocationOfChar = (charLocations.get(startChar).size() > 0) ? charLocations.get(startChar).get(0) : -1;
if(nextLocationOfChar == -1){
break;
}
start=start+1;
done = (nextLocationOfChar > i);
if(done) {
earliestLocationInSubstring.remove(startChar);
}
} while(!done);
if(nextLocationOfChar == -1){
break;
}
}
}
String res = null;
if(bestCoverStart >= 0){
res = s.substring(bestCoverStart, bestCoverStart+bestCoverLength);
}
return res;
}
public static void main(String[] args){
String[] testcases = {"abbcbcba" , "abbcbcbba"};
char[] alphabet = { 'a' , 'b' , 'c' };
for(String s : testcases){
CoverAllCharacters wrapper = new CoverAllCharacters(s);
String cover = wrapper.computeMinCover(alphabet);
System.out.println(s + "\t" + cover);
}
}
}
public class DecimalRepresentaionOfRational {
int numerator;
int denominator;
int quotient;
boolean hasRepeatPattern = false;
int repetitionStart = -1, repetitionEnd = -1;
DecimalRepresentaionOfRational(int numerator, int denominator){
this.numerator = numerator;
this.denominator = denominator;
}
// assume positive
/*
* 22/7
* > 3. 1/7
* > 3.1 3/7
* > 3.14 2/7
* 2 6/7
* 8 4/7
* 5 5/7
* 7 1/7
*
*
* 1/17
* 0.05 15/17
*
*/
void evaluateAndOutput(){
int residual;
int currentQuotient;
quotient = (int) Math.floor(((double) numerator)/denominator);
residual = numerator % denominator;
List<Integer> residuals = new LinkedList<Integer>();
Map<Integer,Integer> residualVsDigits = new HashMap<Integer,Integer>();
boolean done = (residual == 0);
if(!done){
residuals.add(residual);
}
while(!done){
System.out.println("DEBUG: " + residual);
residual = residual*10;
if(residual == 0){
break;
} else if(residual < denominator){
//List<Integer> result = new LinkedList<Integer>();
residualVsDigits.put(residual/10,0);
//result.add(0);
residuals.add(residual);
} else {
currentQuotient = (int) Math.floor(((double) residual)/denominator);
residualVsDigits.put(residual/10,currentQuotient);
residual = residual % denominator;
residuals.add(residual);
}
if(residualVsDigits.containsKey(residual)){
done = true;
hasRepeatPattern = true;
for(int i = 0; i < residuals.size(); i++){
int r = residuals.get(i);
if(r == residual){
if(repetitionStart==-1){
repetitionStart = i;
} else {
repetitionEnd = i-1;
}
}
}
}
}
System.out.println("DEBUG: " + residuals);
System.out.println("DEBUG: " + hasRepeatPattern + " " + repetitionStart + " " + repetitionEnd);
System.out.print( numerator + "/" + denominator + " = " + quotient);
if(residualVsDigits.size() != 0){
System.out.print(".");
}
for(int i = 0; i < residuals.size(); i++){
int r = residuals.get(i);
if(r != 0){
if(hasRepeatPattern){
if(i == repetitionStart){
System.out.print("(");
}
}
System.out.print(residualVsDigits.get(r));
if(hasRepeatPattern){
if(i == repetitionEnd){
System.out.print(")");
break;
}
}
}
}
System.out.println();
}
public static void main(String[] args){
int[] testcaseNumerator = {4 , 2 , 1, 22 , 1 , 1 };
int[] testcaseDenominator = {2 , 4 , 3, 7, 3000, 37};
for(int i = 0; i < 6; i++){
DecimalRepresentaionOfRational wrapper = new DecimalRepresentaionOfRational(testcaseNumerator[i],testcaseDenominator[i]);
wrapper.evaluateAndOutput();
}
}
}
- just_do_it November 17, 2018