madhur.eng
BAN USER 2of 2 votes
AnswersGiven an array and is rotated n number of times find the number where the peak happens. The array is sorted in increasing order. Follow up question: how will you rearrange them in normal sorted order.
 madhur.eng in United States Report Duplicate  Flag  PURGE
Google Software Engineer
Please find the recursive solution and possibly handling all cases where the number in mid is not a single digit.
public class GenerateI18NCombination {
private Set<String> set = new HashSet<String>();
private void recurse(String arr, String strSoFar) {
if (arr.length() > 0) {
set.add(strSoFar);
String replace = replaceNumber(strSoFar, arr.length(), arr.charAt(0), true);
if (!set.contains(replace)) {
String s = arr.substring(1);
recurse(s, replace);
}
replace = replaceNumber(strSoFar, arr.length(), arr.charAt(arr.length()  1), false);
if (!set.contains(replace)) {
String s = arr.substring(0, arr.length()1);
recurse(s, replace);
}
} else {
set.add(strSoFar);
}
}
private String replaceNumber(String str, int length, char ch, boolean isInFront) {
String[] arr = str.split("\\d");
if (length  1 == 0) {
return arr[0] + ch + arr[1];
} else {
if (isInFront) {
return arr[0] + ch + (length  1) + arr[1];
} else {
return arr[0] + (length  1) + ch + arr[1];
}
}
}
public static void main(String[] args) {
GenerateI18NCombination obj = new GenerateI18NCombination();
obj.recurse("AREERCU", "C7P");
List<String> sortedList = new ArrayList<String>(obj.set);
Collections.sort(sortedList);
System.out.println(sortedList);
}
}

madhur.eng
May 22, 2015 Hi By using the containsValue method, you are basically making your implementation run O(N^2) because it take O(N) time to search if that value is there or not. What you can do is save the normal itenary that is given and also a reverse of that itenary i.e. in another hash map store "destination" as key and "source" as value. Now all you have to do is find if the key exists in this second hash map while iterating over the original itenary. I hope I made sense.
 madhur.eng May 22, 2015Hi @um01 can you explain with an example that will be great.
 madhur.eng May 15, 2015Hi, the wording of your algorithm (the last part of calculating the sum) is not clear. If possible please run an example for the same. Thanks.
 madhur.eng May 14, 2015Do the two numbers that we add have to be of same length? for example : Is 1241125 an additive number? (for me it is since 124 +1 =125). But I want to clear it
 madhur.eng May 12, 2015Do the two numbers that we add have to be of same length? for example : Is 1241125 an additive number? (for me it is since 124 +1 =125). But I want to clear it
 madhur.eng May 12, 2015Hello Tony, could you please provide an example, the one you have provided is not very clear. what do you mean by 124 is acceptable if we actually have "126 46.." as key code?
 madhur.eng May 10, 2015Hi, your code seems to work only for numbers that differ by 1 in length. However I think it should't be like that. As per my understanding of code we need to print the two halves that sum up as less than or equal to the other number. Here is my implementation.
public static void splits(String number1, String number2) {
int num = Integer.parseInt(number2);
String half1, half2;
for (int index = 1; index < number1.length(); index++) {
half1 = number1.substring(0, index);
half2 = number1.substring(index);
if ((Integer.parseInt(half1) + Integer.parseInt(half2)) <= num) {
// could be easily changed here to track the halves that sum
// closest to 2nd Number
System.out.println(half1 + "" + half2);
}
}
}

madhur.eng
May 10, 2015 Hello can you explain your code a little bit more as it doesnt make sense what you mean by diameter. BY diameter do you mean its a circle around a rectangle? and then calculating all points? if so how did you calculate the diameter as just square root of area?
 madhur.eng May 10, 2015Hi when you say a Dijkstra's algorithm, how would you do that since it is possible only in a directed graph and this is not.... because if we are able to go from arr[i][j] to arr[i1][j] then reverse is also true... Please correct me if I am wrong. Moreover when you say you would use HEAP DS then do you intend to change the structure of Heap DS as a node can have 2 children but in this question a node can have 4 immediate children (n, s, e, w);
 madhur.eng May 09, 2015Hello amirtar,
This is the code that i wrote. It has a slight modification of saving the best path once i reach a guard and the path i took to reach that guard. This way i save myself from doing a BFS on all nodes.
package arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class GuardEmptySpace {
/*char[][] museum = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}
};*/
char[][] museum = {
{'.', '.', '.', 'G'},
{'.', '.', '.', '.'},
{'G', '#', '#', '.'},
{'.', 'G', '#', '.'}
};
int[][] space = new int[museum.length][museum[0].length];
Queue<String> q;
Set<String> set;
public static void main(String[] args) {
GuardEmptySpace ges = new GuardEmptySpace();
ges.findSpace();
}
private void findSpace() {
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
if (museum[i][j] == 'G') {
//set n, s, e, w to be accessible in just one unit of space if they are not having #
setSpace(i, j);
space[i][j] = Integer.MIN_VALUE;
} else if (museum[i][j] == '#') {
space[i][j] = Integer.MAX_VALUE;
}
}
}
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
q = new LinkedList<String>();
set = new HashSet<String>();
if (space[i][j] == 0) {
set.add(i + "," + j);
q.add(i + "," + j);
setPath(performBFS());
}
}
}
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
if (space[i][j] == Integer.MIN_VALUE) {
System.out.print("G");
} else if (space[i][j] == Integer.MAX_VALUE) {
System.out.print("#");
} else {
System.out.print(space[i][j]);
}
}
System.out.println();
}
}
private void setPath(String s) {
String[] split = s.split(";");
int k = 1;
for (int i = split.length  2; i >= 0; i, k++) {
String[] split2 = split[i].split(",");
space[Integer.parseInt(split2[0])][Integer.parseInt(split2[1])] = k;
}
}
private String performBFS() {
int i, j;
while (!q.isEmpty()) {
StringBuilder sb = new StringBuilder(q.poll());
String str = getIndexString(sb.toString());
String[] split = str.split(",");
i = Integer.parseInt(split[0]);
j = Integer.parseInt(split[1]);
if (museum[i][j] == 'G') {
return sb.toString();
} else {
changeQueue(sb.toString(), i  1, j);
changeQueue(sb.toString(), i + 1, j);
changeQueue(sb.toString(), i, j  1);
changeQueue(sb.toString(), i, j + 1);
}
}
return "";
}
private void changeQueue(String str, int i, int j) {
StringBuilder sb = new StringBuilder(str);
if (isGoodCell(i, j)) {
q.add(sb.append(";").append(i).append(",").append(j).toString());
set.add(i + "," + j);
}
}
private String getIndexString(String str) {
String[] split = str.split(";");
int size = split.length;
return split[size  1];
}
private boolean isGoodCell(int i, int j) {
if ((i < museum.length && i >= 0) && (j < museum[0].length && j >= 0)) {
if ((!set.contains(i + "," + j)) && (space[i][j] != Integer.MAX_VALUE)) {
return true;
}
}
return false;
}
private void setSpace(int i, int j) {
// set north
if ((i  1 >= 0) && (space[i  1][j] != '#')) {
space[i  1][j] = 1;
}
// set south
if ((i + 1 < museum.length) && (space[i + 1][j] != '#')) {
space[i + 1][j] = 1;
}
//set east
if ((j  1 >= 0) && (space[i][j  1] != '#')) {
space[i][j  1] = 1;
}
if ((j + 1 < museum[0].length) && (space[i][j + 1] != '#')) {
space[i][j + 1] = 1;
}
}
}

madhur.eng
May 09, 2015 i think we can save ourself from doing BFS on N nodes. Here is what i propose:
(1) first traverse the whole array and while traversing whenever you find a G, we turn all the accessible points from that G with distance of 1 only as 1, i.e. the immediate n, s, e, w points to this G as 1. and keep putting these cells in a queue.
(2) while the queue is not empty, we pop one element (one cell) and turn it's n, s, e, w to be min(it's neighbors + 1); and put this new cell in queue.
NOTE: since not all the neighbors are having the value we just take those that have and we shall check this value again. Also the cells that have value as 1 cannot be better than that so we don't enqueue them again.
Please reply if you find any ambiguity in the algorithm.
You need to create a min heap of k size which will take O(n) and then after heap creation just pop all elements one by one and add the total number of stones needed to overflow each pot.
 madhur.eng May 05, 2015Well the person who down flagged it please be courteous enough to drop the reason for the same. Also this solution works as I have tried and tested it using JAVA
 madhur.eng April 19, 2014My solution is O(n), assuming, we need to give a pair of numbers whose sum matches the value asked for.
(1) create a hash map of <key=(the numbers given in list), value= the frequency of the number>
(2) start with first number in the list and subtract this number from the sum (if the number is positive), if its negative then add.
(3) search in hash map for the difference from step 2 if present then print the pair else proceed with step 2.
Note: few assumptions
(1) sum requested is positive, but the above algo can be modified to make it work for
negative sums.
(2) we want to print pair of numbers only.
this is not a recursive solution....
 madhur.eng April 08, 2014What do you mean by ^ operator?
 madhur.eng April 08, 2014I am down voting the same because the use of regex expression is the best way to do so as that is much more quicker and clean.
 madhur.eng April 06, 2014the approach is correct but it will be O(n^2) not O(n*logn)
 madhur.eng April 04, 2014I would do it in the following way....
Step 1: Iterate through all the elements in the list
Step 2: Insert each element in a set if its not there, else remove from the set.
Step 3: once end of list occurs, Iterate through the set and print if any element, else "print no unique element"
/*
* Returns true if the input string is a number and false otherwise
*/
/*
* Examples:
* isNumber(12) > true
* isNumber("one") > false
* isNumber(23.2) > true
* isNumber(0) > true
* isNumber(23) > true
*/
public static boolean isNumber(String toTest)
{
boolean flag = false;
// implementation here
String pattern = "(?\\d+)(?\\d+\\.\\d+)";
flag = toTest.matches(pattern);
return flag;
}
 madhur.eng April 04, 2014
Just a small suggestion that when you do this
, then it might throw an overflow exception. the correct way is to
 madhur.eng June 03, 2015