MaYanK
BAN USER- 2of 2 votes
AnswersHe showed me a game on his android phone. some sort of maze. There is ball at starting point ball can move in 4 direction at max if there is no wall. End point is hole you need to write code to solve this problem. Idea is convert it into graph and do the DFS to find the path from start to end.
- MaYanK| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm - 1of 1 vote
AnswersGiven a sorted array which contains scores range from 0 to 100. Write a program to find occurrence of given score.
- MaYanK
eg. 1,1,1,40,40,40,100,100
input: 40
o/p : 3 (as 40 appear 3 times in array)| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm
Recurrence
T[i] = T[k] & isValidWord(k+1,i); where k=0 to i;
T[0] = True;
T is boolean vector.
Where T[i] means sentence can be form with i char of given string.
isValidWord(k+1,i) means word formed with char start from position k+1 to i both inclusive present in dictionary or not. If yes then true else false.
<pre lang="java" line="1" title="CodeMonkey949" class="run-this">import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class DP4 {
public static void main(String args[]) throws FileNotFoundException {
ArrayList<String> aDictionary = new ArrayList<String>();
Scanner sc = new Scanner(new File("E:\\Notes\\twl06.txt"));
while (sc.hasNext()) {
aDictionary.add(sc.next());
}
String sentence = "$itwasthebestoftimes";
correctSentence(sentence, aDictionary);
}
private static void correctSentence(String sentence,
ArrayList<String> aDictionary) {
// TODO Auto-generated method stub
int n = sentence.length();
boolean[] words = new boolean[n];
words[0] = true;
int[] path = new int[n];
for (int i = 1; i < n; i++) {
for (int k = 0; k < i; k++) {
if (words[k]
&& aDictionary.contains(sentence
.substring(k + 1, i + 1))) {
path[i]=k;
words[i] = true;
}
}
}
printSentence(sentence,path,n-1);
}
private static void printSentence(String sentence,int[] path, int n) {
// TODO Auto-generated method stub
if(n==0)return;
printSentence(sentence, path,path[n]);
System.out.print(" "+sentence.substring(path[n]+1,n+1));
}
}
</pre><pre title="CodeMonkey949" input="yes">
</pre>
This is My second Logic as mentioned in first post.
A= { 10, 10, 10, 10, 10, 20, 20, 20, 30, 30, 40, 40, 100, 100, 100 };
If you want to find occurrence of 20.
1)binary search for 20-0.5 = 19.5
it will return lowIndex = 4.
2)BinarySearch for 20+0.5 =20.5
It will return highIndex = 7
Occurrence of 20 = highIndex - lowIndex = 7-4 =3
<pre lang="java" line="1" title="CodeMonkey19340" class="run-this">/* Note : we don't need array b according to problem I am keeping to
test my program for finding occurrences of all score.*/
class BinarySearch {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[] { 10, 10, 10, 10, 10, 20, 20, 20, 30, 30, 40, 40,
100, 100, 100 };
int[] b = { 10, 20, 30, 40, 100 };
for (int i = 0; i < b.length; i++) {
float l = (float) b[i] - 0.5f;
float h = (float) b[i] + 0.5f;
int lowerIndex = binarySearch(a, 0, a.length - 1, l);
int highIndex = binarySearch(a, 0, a.length - 1, h);
System.out.println(b[i] + " repeated: " + (highIndex - lowerIndex)
+ " times");
}
}
private static int binarySearch(int[] a, int low, int high, float k) {
while (low <= high) {
//<= very Important
int mid = low + (high - low) / 2;
if (a[mid] < k) {
low = mid + 1;
} else if (a[mid] > k) {
high = mid - 1;
} else {
return mid;
}
}
return high;
}
}
</pre><pre title="CodeMonkey19340" input="yes">
</pre>
public class LongestPalindrom {
public static void main(String args[]) {
String str = " hello . you uoy era woh..";
char[] a = str.toCharArray();
int low = Integer.MAX_VALUE;
int upper = Integer.MIN_VALUE;
for (int i = 0; i < str.length(); i++) {
int start = i;
int end = i;
while (start >= 0 && end < str.length()) {
if (a[start] == a[end]) {
if (end - start > upper - low) {
upper = end;
low = start;
}
end++;
start--;
} else {
break;
}
}
}
for (int i = 0; i < str.length(); i++) {
int start = i;
int end = i + 1;
while (start >= 0 && end < str.length()) {
if (a[start] == a[end]) {
if (end - start > upper - low) {
upper = end;
low = start;
}
end++;
start--;
} else {
break;
}
}
}
for (int i = low; i <= upper; i++) {
System.out.print(a[i]);
}
}
}
@ibnipun10
I think we have to prove that only some combinations are valid
for odd digit two combinations need to be considered and checked
25126 = 25,1,26 or 2,51,26
For even digit only one combination need to be considered
121224 = 12,12,24
if I try another combinations it seems not possible.
I took some time to understand the game also played 2 minute and in last 15 minute I wrote this way exactly so there could be some bug
class Point{
int id;
Point left;
Point right;
Point top;
Point bottom;
boolean visit;
}
public boolean dfsVisit(Point start,Point end ,String path){
start.visit = true;
if(start.id==end.id)
{
System.out.println("Path:"+path);
return true;
}
if(isValid(start.left) && dfsVisit(start.left,end,start.id+path)
return true;
if(isValid(start.right) && dfsVisit(start.right,end,start.id+path)
return true;
if(isValid(start.top) && dfsVisit(start.top,end,start.id+path)
return true;
if(isValid(start.bottom) && dfsVisit(start.bottom,end,start.id+path)
return true;
return false;
}
public boolean isValid(Point p)
{
if(p==null) return false;
if(p.visit) return false;
return true;
}
Solution 1 : I said binary search for score in this example 40 which in turn will give and index and then have two pointer one goes left and one go right and count the 40.
worst case O(n) if all numbers are 40.
Solution 2 : Modify the binary search such that when element does not exists it return s low index. and then do binary search 39.5 and 40.5 (score-0.5 and score +0.5)
searching 39.5 will give you index 2 which is one less than start index of 40.
searching 0.5 will give you index 6 which is one more than end index of 40.
He did not ask me to code this just want to have idea. I told him we need to handle some edge condition.
<pre lang="java" line="1" title="CodeMonkey31871" class="run-this">class Permutation1 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
permute2("abcd", "ab"); //output permutation should not contain ab
}
private static void permute2(String input, String filter) {
// TODO Auto-generated method stub
permute2("", input, filter, "");
}
private static void permute2(String soFar, String rest, String filter,
String filterSoFar) {
// TODO Auto-generated method stub
//if accumulated filter is equal to given filter dont print and return
if (filter.equals(filterSoFar)) {
return;
}
if (filter.length() == filterSoFar.length()) {
filterSoFar = filterSoFar.substring(1);
}
if (rest.equals("")) {
System.out.println(soFar);
return;
}
//While considering a choice accumulate the filter also
for (int i = 0; i < rest.length(); i++) {
char ch = rest.charAt(i);
String next = soFar + ch;
String remain = rest.substring(0, i) + rest.substring(i + 1);
permute2(next, remain, filter, filterSoFar + ch);
}
}
}
</pre><pre title="CodeMonkey31871" input="yes">
</pre>
<pre lang="java" line="1" title="CodeMonkey11169" class="run-this">//Sorry In previous code I forgot to initialize the table
class KIncreasing {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = {6,3,4,1,7,8};
int k = 4;
findKIncrasing(input, k);
}
private static void findKIncrasing(int[] input, int k) {
// TODO Auto-generated method stub
int[] sums = new int[input.length]; //lonngest sum
int[] sol = new int[input.length]; //finding path
int[] size = new int[input.length]; //size of sequence
//Forgot to Initialize this in previous code
for (int i = 0; i < input.length; i++) {
sums[i] = input[i];
size[i] = 1;
sol[i] = -1;
}
int max = Integer.MIN_VALUE;
int index = -1;
for (int i = 1; i < input.length; i++) {
for (int j = 0; j < i; j++) {
if (input[i] > input[j] && sums[i] < input[i] + sums[j]) {
sums[i] = input[i] + sums[j];
size[i] = 1 + size[j];
sol[i] = j;
}
}
if (size[i] >= k) {
int j = k;
int m = i;
int sum = 0;
while (j > 0) {
sum = sum + input[m];
m = sol[m];
j--;
}
if (sum > max) {
index = i;
max = sum;
}
}
}
if (index == -1) {
System.out.print("No sequence of size k");
return;
}
System.out.println("max:" + max);
System.out.println("index:" + index);
System.out.print("sequence:-");
printSeq(index, input, sol, k);
}
private static void printSeq(int index, int[] input, int[] sol, int k) {
// TODO Auto-generated method stub
if (k == 0)
return;
printSeq(sol[index], input, sol, k - 1);
System.out.printf("%3d,", input[index]);
}
}
</pre><pre title="CodeMonkey11169" input="yes">
</pre>
@ibnipun10 I did not understand your method first we need k increasing sequence with max sum.
You said max heap
1,5,2,8,7,6,11
k=3
initial heap contain 1,5,2 which is not increasing sequence.
now 8 is there remove 5 and got 1,2,8
now remove 8 and insert
1,2,11
but answer 5,8,11
<pre lang="java" line="1" title="CodeMonkey68377" class="run-this">class KIncreasing {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = {1,5,2,8,7,6,11};
int k = 3;
findKIncrasing(input, k);
}
private static void findKIncrasing(int[] input, int k) {
// TODO Auto-generated method stub
int[] sums = new int[input.length];
int[] sol = new int[input.length];
int[] size = new int[input.length];
sums[0] = input[0];
size[0] = 1;
sol[0] = -1;
int max = Integer.MIN_VALUE;
int index = -1;
for (int i = 1; i < input.length; i++) {
for (int j = 0; j < i; j++) {
if (input[i] > input[j] && sums[i] < input[i] + sums[j]) {
sums[i] = input[i] + sums[j];
size[i] = 1 + size[j];
sol[i] = j;
}
}
if (size[i] >= k) {
int j = k;
int m = i;
int sum = 0;
while (j > 0) {
sum = sum + input[m];
m = sol[m];
j--;
}
if (sum > max) {
index = i;
max = sum;
}
}
}
if (index == -1) {
System.out.print("No sequence of size k");
return;
}
System.out.println("max:" + max);
System.out.println("index:" + index);
System.out.print("sequence:-");
printSeq(index, input, sol, k);
}
private static void printSeq(int index, int[] input, int[] sol, int k) {
// TODO Auto-generated method stub
if ( k == 0)
return;
printSeq(sol[index], input, sol, k-1);
System.out.printf("%3d,", input[index]);
}
}
</pre><pre title="CodeMonkey68377" input="yes">
</pre>
JD give us very good logic for this problem on chatterous. We will covert BST to Circular Doubly LinkedList in-place.
Then normal two pointer logic
here is the logic for converting BST To DLL
private static TreeNode<Integer> bstToList(TreeNode<Integer> root) {
// TODO Auto-generated method stub
if (root == null)
return null;
TreeNode<Integer> first = bstToList(root.left);
TreeNode<Integer> second = bstToList(root.right);
// Merge first with root and then root with second
root.left = root;
root.right = root;
TreeNode<Integer> aList = append(first, root);
aList = append(aList, second);
return aList;
}
private static TreeNode<Integer> append(TreeNode<Integer> first,
TreeNode<Integer> second) {
// TODO Auto-generated method stub
TreeNode<Integer> l = null;
TreeNode<Integer> r = null;
if (first == null) {
if (second.left == null)
second.left = second;
if (second.right == null)
second.right = second;
return second;
}
if (second == null) {
if (first.left == null)
first.left = first;
if (first.right == null)
first.right = first;
return first;
}
l = first.left;
r = second.left;
l.right = second;
second.left = l;
first.left = r;
r.right = first;
return first;
}
Full code is here ideone com/5mGIM for BST to DLL
Based on following link cslibrary stanford edu/109/TreeListRecursion html
This is DFS
I will start from(0,0) and
Step1:is to check is It possible to visit (i,j) isEmpty() method take care of that.
If yes : mark it visited and go to step 2.
If No : return false;
STEP2:
At each step you have 4 possible move UP,DOWN,RIGHT,LEFT
You explore each path. we continue until we reach at destination cell.
Basically we are exploring all the path for example 3x3 Puzzle
true false true
true false false
true true true
VisitMarker
false false false
false false false
false false false
(0,0) = isPossible move
visit[0,0] = true;
4 possible move from here
Say we go RIGHT i.e. call dfsVisit(0,1);
maze[0,1] = False so not valid move return false;
Similarly Try LEFT and TOP which out of maze boundary.
so Try DOWN i.e call dfsVisit(1,0)
maze[1,0] = true
visit[1,0] and then explore from there. till you reach at destination.
<pre lang="java" line="1" title="CodeMonkey98301" class="run-this">//Good Version than previous one
import java.util.Random;
class MazeDriver {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//Maze m = new Maze();
boolean cells[][]=
{
{true,false,true},
{true,false,false},
{true,true,true}
};
Maze m = new Maze(cells);
System.out.println(m.isSolvable());
}
}
class Maze{
private final boolean[][] cells;
private final boolean[][] visit;
public Maze(){
cells = new boolean[10][10];
visit = new boolean[10][10];
init();
}
public Maze(boolean[][] cells){
this.cells = cells;
visit = new boolean[cells.length][cells.length];
}
private void init() {
// TODO Auto-generated method stub
Random r = new Random();
for(int i=0;i<cells.length;i++){
for(int j=0;j<cells.length;j++){
cells[i][j] = r.nextBoolean();
}
}
}
private boolean isEmpty(int x,int y){
if(x<0 || x>=cells.length || y<0 ||y>=cells.length)
return false;
if(visit[x][y])
return false;
return cells[x][y];
}
public boolean isSolvable(){
return dfsVisit(0,0);
}
private boolean dfsVisit(int i, int j) {
// TODO Auto-generated method stub
if(!isEmpty(i, j))
return false;
visit[i][j]=true;
if(i==cells.length-1 && j==cells.length-1)
return true;
if(dfsVisit(i+1, j)){
return true;
}
if(dfsVisit(i, j+1)){
return true;
}
if(dfsVisit(i-1, j)){
return true;
}
if(dfsVisit(i, j-1)){
return true;
}
return false;
}
}</pre><pre title="CodeMonkey98301" input="yes">
</pre>
<pre lang="java" line="1" title="CodeMonkey11873" class="run-this">import java.util.Random;
class MazeDriver {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//Maze m = new Maze();
boolean cells[][]=
{
{true,false,true},
{true,false,false},
{true,true,true}
};
Maze m = new Maze(cells);
System.out.println(m.isSolvable());
}
}
class Maze{
private final boolean[][] cells;
private final boolean[][] visit;
public Maze(){
cells = new boolean[10][10];
visit = new boolean[10][10];
init();
}
public Maze(boolean[][] cells){
this.cells = cells;
visit = new boolean[cells.length][cells.length];
}
private void init() {
// TODO Auto-generated method stub
Random r = new Random();
for(int i=0;i<cells.length;i++){
for(int j=0;j<cells.length;j++){
cells[i][j] = r.nextBoolean();
}
}
}
private boolean isEmpty(int x,int y){
if(x<0 || x>=cells.length || y<0 ||y>=cells.length)
return false;
if(visit[x][y])
return false;
return cells[x][y];
}
public boolean isSolvable(){
return dfsVisit(0,0);
}
private boolean dfsVisit(int i, int j) {
// TODO Auto-generated method stub
visit[i][j]=true;
if(i==cells.length-1 && j==cells.length-1)
return true;
if(isEmpty(i+1, j) && dfsVisit(i+1, j)){
return true;
}
if(isEmpty(i, j+1) && dfsVisit(i, j+1)){
return true;
}
if(isEmpty(i-1, j) && dfsVisit(i-1, j)){
return true;
}
if(isEmpty(i, j-1) && dfsVisit(i, j-1)){
return true;
}
return false;
}
}</pre><pre title="CodeMonkey11873" input="yes">
</pre>
Well I think we can build array of suffixes and then sort them.
e.g. mayank
mayank| ayank |yank |ank |nk| k
sort them
ank| ayank| k| mayank| nk |yank|
now two adjacent which has longest prefix is our answer
in this example "a" from (ank and ayank).
This is easy and standard solution.
class StringPermutation {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = "abb";
permutation(input, "");
}
private static void permutation(String input, String sofar) {
// TODO Auto-generated method stub
if (input.equals("")) {
System.out.printf("%s,", sofar);
}
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (input.indexOf(c, i + 1) != -1)
continue;
permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
}
}
}
<pre lang="java" line="1" title="CodeMonkey51041" class="run-this">// Code is huge but surely work this O(nlogn) according to coreman books hint
import java.util.Random;
class Inversions {
public static void main(String args[]) // entry point from OS
{
int[] a = new int[5];
int[] b = new int[5];
int[] c = new int[5];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(37);
b[i] = i;
System.out.printf("%3d", a[i]);
}
System.out.println();
System.out.println("Total Inversion:-"
+ mergeSort(a, b, c, 0, a.length - 1));
System.out.print("Pairs:-");
for (int i = 0; i < a.length; i++) {
System.out.printf("(%3d,%3d)", i, c[i]);
}
}
private static int mergeSort(int[] a, int[] b, int[] c, int p, int r) {
// TODO Auto-generated method stub
int count = 0;
if (p < r) {
int q = (p + r) / 2;
count = mergeSort(a, b, c, p, q);
count += mergeSort(a, b, c, q + 1, r);
count += merge(a, b, c, p, q, r);
}
return count;
}
private static int merge(int[] a, int[] b, int[] c, int p, int q, int r) {
// TODO Auto-generated method stub
int[] left = new int[q - p + 1];
int[] right = new int[r - q];
int[] left1 = new int[q - p + 1];
int[] right1 = new int[r - q];
for (int i = 0; i < left.length; i++) {
left[i] = a[p + i];
left1[i] = b[p + i];
}
for (int i = 0; i < right.length; i++) {
right[i] = a[i + q + 1];
right1[i] = b[i + q + 1];
}
int count = 0;
int x = 0;
int i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
a[p] = left[i];
b[p] = left1[i];
c[b[p]] += x;
count = count + x * 1;
p++;
i++;
} else {
x++;
a[p] = right[j];
b[p] = right1[j];
p++;
j++;
}
}
while (i < left.length) {
a[p] = left[i];
b[p] = left1[i];
count = count + x * 1;
c[b[p]] += x;
i++;
p++;
}
while (i < right.length) {
a[p] = right[i];
b[p] = right1[i];
i++;
p++;
}
return count;
}
}
</pre><pre title="CodeMonkey51041" input="yes">
</pre>
private static LinkedList merge(Node a, Node b) {
// TODO Auto-generated method stub
LinkedList merge = new LinkedList();
Node dummy=new Node();
Node tail = dummy;
while(a!=null && b!=null){
if(a.data<b.data){
tail.next = a;
a= a.next;
tail = tail.next;
}
else{
tail.next = b;
b=b.next;
tail = tail.next;
}
}
if(a==null){
tail.next = b;
}
if(b==null){
tail.next =a;
}
merge.root = dummy.next;
return merge;
}
<pre lang="java" line="1" title="CodeMonkey36091" class="run-this">import java.util.Arrays;
class SUM3 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = { 5, 10, 91, -9, -11, -4, -20, -70,-80, 25, -20, -5, -15 };
printTriplets(a);
}
private static void printTriplets(int[] a) {
// TODO Auto-generated method stub
Arrays.sort(a);
for (int i = 0; i < a.length; i++) {
int j = i + 1;
int k = a.length - 1;
while (j < k) {
if ((a[j] + a[k] + a[i]) > 0) {
k--;
} else if ((a[j] + a[k] + a[i]) < 0) {
j++;
} else {
System.out.println("Tripletes Are:");
System.out.printf("(%3d,%3d,%3d)",a[i],a[j],a[k]);
System.out.println();
j++;
k--;
}
}
}
}
}
</pre><pre title="CodeMonkey36091" input="yes">
</pre>
Reppamulapaya2, Area Sales Manager at Alcatel Lucent
Jorie , a Customer services manager with more than 6 years' experience working is responsible for managing the relationships between an ...
Repmikebeasley033, Interviewer at Brooks Fashions
Working as an interviewer in Brooks Fashion's best amazing experience . Here I manage individuals which makes me refreshed . With ...
RepRafaelLisa, Librarian at Cut Above
I am a librarian . responsible for selecting, organizing, and delivering information materials in a variety of formats such as electronic ...
RepRenitaLoius, Digital marketing freshers at Amdocs
Renita , a marketing writer with a comprehensive background of achievements in providing marketing advice to clients, writing original articles on ...
Repracheljennir, Personnel consultant at Infinite Wealth
Rachel, I am a Personnel consultant who acts as mediator between employers and job seekers. The main task of I ...
ok
- MaYanK December 24, 2010