HauntedGhost
BAN USER- 0of 0 votes
AnswersGiven coordinates (X[i],Y[i]) of all the cities in the world(for simplicity lets consider we have 2D world map). You are given a user's location (x,y), find out the closest city to the user. Write code for it.
- HauntedGhost in United States
Update:
Time complexity of the solution should be better than O(n) as there will be multiple lookup queries with different input points.
You can preprocess the data in any way you like, but you need to minimize the query execution time complexity.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven an array of 0s and 1s, find out:
- HauntedGhost in United States
1. all the subsequences where number of 0s = number of 1s
2. max length subsequence where number of 0s = number of 1s
Update:
We need to find subarrays, not subsequences. Sorry for the confusion.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
I think problem is missing the complete example. In excel, cells are named as A,B,..Z, AA,AB,..AZ, BA,BB...BZ, AAA,AAB,...AAZ.. and so on.
if this is the case, it is nothing but a base conversion of decimal number to base 26 number!
small code to solve it :
public static String convert(int number) {
String ans = "";
int base = 0;
while(number > 0) {
ans = (char)(number%26-1+'A') + ans;
number /= 26;
}
return ans;
}
@xq - time complexity of DP solution is O(n) as you calculate each i only once.
time complexity of recursive method is 2^(n-1) worst case.
Worst case is: {2,2,2,2} when at each first n-1 positions you have two options - either eat just current digit, or eat the next digit also.
@jerryyue1908 here is the DP version of it -
public static int DP(int []a, int n) {
int [] dp = new int [n+1];
dp[0] = 0;
for(int i=1; i<=n; i++) {
if(i>1 && a[i-2] <= 2 && a[i-1] <= 6) {
dp[i] = dp[i-1] + dp[i-2] + 1;
} else {
dp[i] = dp[i-1];
}
}
return dp[n]+1; // +1 for base case where all characters are made of single digits
}
It is easy to generate all strings from dp matrix. However, it will take same time as generating from the given array. So I wrote simple code for generating strings from the given array, which returns the number of strings as well -
public static int print(int [] a, int i, int n, String s) {
if(i == n) {
System.out.println(s);
return 0;
}
int ans = 0;
if(i < n-1 && a[i+1] <= 6 && a[i] <= 2) {
ans += print(a, i+2, n, new String(s+(char)(a[i]*10+a[i+1]+'a'-1))) +1;
}
ans += print(a, i+1, n, new String(s+(char)(a[i]+'a'-1)));
return ans;
}
I used remaining bits of the given numbers to store the next value of a[i] i.e. a[a[i]]. Here is the code -
public static void relocate(int a[], int n) {
int size = n;
int bits = 0;
// calculate no. of bits
while(size > 0) {
bits += 1;
size >>= 1;
}
// generate a mask of all 1s of bits size from least significant bit
int mask = 0;
for(int i=0; i<bits; i++) {
mask <<= 1;
mask |= 1;
}
// store the number to be replaced in the same number but different in the remaining unused bits
// i.e. if a number has only 3 bits set, it will look like ..00000xxx (so we can use other bits to store the new value in it)
// first left shift the a[a[i]] to bit size so result will be ..00yyy000 and then take OR with a[i]
// it becomes ..00yyyxxx where yyy is a[a[i]], and xxx is the a[i]
// one thing to remember is that, we need to normalize a[a[i]] before shifting left. i.e. instead of considering ..00yyyxxx and shift it
// we need to shift only ..00000xxx so I created a mask to do that, a[a[i]] & mask i.e. (..00yyyxxx|..00000111) and then shift left
for(int i=0; i<n; i++) {
a[i] = ((a[a[i]]&mask) << bits) | (a[i]);
}
// finally to get the new value for each a[i] (which is of form ..00yyyxxx right now) we need to shift it by "bits" size
// so a[i] >> bits should do the trick!
for(int i=0; i<n; i++) {
a[i] = a[i] >> bits;
}
}
a little bit simpler idea and implementation -
public void kPalindrome() {
char [] s= "zayxcbbcxa".toCharArray();
int k = 2;
int n = s.length;
int [][] dp = new int[n+1][n+1];
dp[0][0] = 0;
for(int i=1; i<=n; i++) dp[i][0] = dp[0][i] = i;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
dp[i][j] = Math.min(dp[i][j-1] + 1, dp[i-1][j] + 1);
if(s[i-1] == s[n-j]) { // compare 0th with n-1th, 1st with n-2th and so on
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j]);
}
}
}
// this is tricky, we get the min deletions possible to compare given string and its reverse
// so dp[n][n] includes, deletions performed on string plus deletions performed on its reverse
// hence we divide it by 2 to get the number of deletions required to make it a palindrome
// and trust me dp[n][n] will always be even number ;)
if(dp[n][n]/2 > k) System.out.println("NO");
else System.out.println("YES");
}
Dynamic programming solution, comments inline :
public boolean regexMatch(String word, String pattern) {
int wordLength = word.length(), patternLength = pattern.length();
boolean [][] dp = new boolean [wordLength+1][patternLength+1];
dp[0][0] = true;
for(int i=1; i<=patternLength; i++) {
// assuming '*' will never be the first letter
if(i < patternLength && pattern.charAt(i) == '*') {
dp[0][i] = dp[0][i + 1] = dp[0][i - 1];
i += 1;
}
else break;
}
for(int i=1; i<=wordLength; i++) {
for(int j=1; j<=patternLength; j++) {
// if the next letter in pattern is '*'
if(j < patternLength && pattern.charAt(j) == '*') {
dp[i][j] = dp[i][j+1] = (dp[i][j-1]) || // current word substring already matched in previous pattern
(dp[i-1][j-1] && (word.charAt(i-1) == pattern.charAt(j-1))) || // prev word substring already matched in prev pattern
(dp[i-1][j] && (word.charAt(i-1) == pattern.charAt(j-1))); // prev word substring matched with current pattern
j += 1; // increment by one more
} else {
// current letter of word must match with pattern's current letter
// and also last substring of word should also match with last substring of pattern
dp[i][j] = dp[i-1][j-1] && (word.charAt(i-1) == pattern.charAt(j-1));
}
}
}
return dp[wordLength][patternLength];
}
Ignore my previous solution, that's incomplete. I'm trying to edit that, but it's not working.
Dynamic programming based approach.
Maintain a matrix DP[0..n+1][0..sum+1]
where DP[i][j] = 1 if there is a subset in A[0...i-1] whose sum is equal to j
Recurrence equation
DP[i][j] = 1 if DP[i-1][j] == 1 // if the sum j is possible in A[0..i-1]
or if DP[i-1][j-A[i]] == 1 // if sum j-A[i] is possible in A[0..i-1]
Base case
DP[0..n][0] = 1 // sum zero is always possible
public static void findSubsets(int []a) {
int [][] dp = new int [a.length+1][1000]; // assume max sum is 1000
int sum = 0;
for(int i=0; i<a.length; i++) sum += a[i];
for(int i=0; i<a.length+1; i++) dp[i][0] = 1; // sum zero is always possible
for(int i=1; i<=a.length; i++) {
for(int s=1; s<=sum; s++) {
if(s >= a[i-1])
dp[i][s] = Math.max(dp[i-1][s], dp[i-1][s-a[i-1]]); // add or skip current item
else dp[i][s] = dp[i-1][s]; // otherwise check if this was possible in a[0..i-1] subarray
}
}
int halfSum = sum/2;
int partition1 = 0;
for(int s=halfSum; s>=0; s--) {
if(dp[a.length][s] == 1) { // if sum s is possible in the array
partition1 = s;
break;
}
}
int partition2 = sum - partition1;
System.out.println("Two partitions: sum1: " + partition1 + ", sum2: " + partition2);
}
Above solution will work but it won't split the partitions in equal numbers. To achieve that we need to keep track of counts of the elements in subsets as well.
So the new equation will be --
Maintain a matrix DP[0..n+1][0..sum+1][0...n+1]
where DP[i][j][n] = 1 if there is a subset in A[0...i-1] whose sum is equal to j WITH COUNT n is possible
Recurrence equation
DP[i][j][n] = 1 if DP[i-1][j][n] == 1 // if the sum j is possible in A[0..i-1] with count n
or if DP[i-1][j-A[i]][n-1] == 1 // if sum j-A[i] is possible in A[0..i-1] with count n-1
Base case
DP[0..n][0][0] = 1 // sum zero with count 0 is always possible
Working code:
public static void findSubsets(int [] a) {
// array length is not even, we can't partition that in equal partitions
if(a.length%2 != 0) {
System.out.println("Balanced partition not possible.");
return;
}
int sum = 0;
for(int i=0; i<a.length; i++) sum += a[i];
int [][][] dp = new int[a.length+1][sum+1][a.length+1];
// sum zero with zero elements is always possible
for(int i=0; i<=a.length; i++) dp[i][0][0] = 1;
for(int i=1; i<=a.length; i++) {
for(int s=1; s<=sum; s++) {
for(int n=1; n<=a.length; n++) {
if(s >= a[i-1])
dp[i][s][n] = Math.max(dp[i-1][s][n], dp[i-1][s-a[i-1]][n-1]);
else
dp[i][s][n] = dp[i-1][s][n];
}
}
}
int halfSum = sum/2;
int halfCount = a.length/2;
int partition1=0, partition2=0;
for(int s=halfSum; s>=0; s--) {
if(dp[a.length][s][halfCount] == 1) {
partition1 = s;
break;
}
}
partition2 = sum - partition1;
System.out.println(
"Partition found with " + a.length / 2
+ " elements: sum1: "
+ partition1
+ ", sum2: " + partition2);
}
Above solution will work for finding partitions with sum S and with any number of elements.
Hope this helps.
Dynamic programming based approach.
Maintain a matrix DP[0..n+1][0..sum+1]
where DP[i][j] = 1 if there is a subset in A[0...i-1] whose sum is equal to j
Recurrence equation
DP[i][j] = 1 if DP[i-1][j] == 1 // if the sum j is possible in A[0..i-1]
or if DP[i-1][j-A[i]] == 1 // if sum j-A[i] is possible in A[0..i-1]
Base case
DP[0..n][0] = 1 // sum zero is always possible
public static void findSubsets(int []a) {
int [][] dp = new int [a.length+1][1000]; // assume max sum is 1000
int sum = 0;
for(int i=0; i<a.length; i++) sum += a[i];
for(int i=0; i<a.length+1; i++) dp[i][0] = 1; // sum zero is always possible
for(int i=1; i<=a.length; i++) {
for(int s=1; s<=sum; s++) {
if(s >= a[i-1])
// add or skip current item
dp[i][s] = Math.max(dp[i-1][s], dp[i-1][s-a[i-1]]);
// otherwise check if this was possible in a[0..i-1] subarray
else dp[i][s] = dp[i-1][s];
}
}
int halfSum = sum/2;
int partition1 = 0;
for(int s=halfSum; s>=0; s--) {
if(dp[a.length][s] == 1) { // if sum s is possible in the array
partition1 = s;
break;
}
}
int partition2 = sum - partition1;
System.out.println("Two partitions: sum1: " + partition1 + ", sum2: " + partition2);
}
Above solution will work but it won't split the partitions in equal numbers. To achieve that we need to keep track of counts of the elements in subsets as well.
So the new equation will be --
Maintain a matrix DP[0..n+1][0..sum+1][0...n+1]
where DP[i][j][n] = 1 if there is a subset in A[0...i-1] whose sum is equal to j WITH COUNT n is possible
Recurrence equation
DP[i][j][n] = 1 if DP[i-1][j][n] == 1 // if the sum j is possible in A[0..i-1] with count n
or if DP[i-1][j-A[i]][n-1] == 1 // if sum j-A[i] is possible in A[0..i-1] with count n-1
Base case
DP[0..n][0][0] = 1 // sum zero with count 0 is always possible
Working code:
public static void findSubsets(int [] a) {
// array length is not even, we can't partition that in equal partitions
if(a.length%2 != 0) {
System.out.println("Balanced partition not possible.");
return;
}
int sum = 0;
for(int i=0; i<a.length; i++) sum += a[i];
int [][][] dp = new int[a.length+1][sum+1][a.length+1];
// sum zero with zero elements is always possible
for(int i=0; i<=a.length; i++) dp[i][0][0] = 1;
for(int i=1; i<=a.length; i++) {
for(int s=1; s<=sum; s++) {
for(int n=1; n<=a.length; n++) {
if(s >= a[i-1])
dp[i][s][n] = Math.max(dp[i-1][s][n],
dp[i-1][s-a[i-1]][n-1]);
else
dp[i][s][n] = dp[i-1][s][n];
}
}
}
int halfSum = sum/2;
int halfCount = a.length/2;
int partition1=0, partition2=0;
for(int s=halfSum; s>=0; s--) {
if(dp[a.length][s][halfCount] == 1) {
partition1 = s;
break;
}
}
partition2 = sum - partition1;
System.out.println(
"Partition found with " + a.length / 2
+ " elements: sum1: "
+ partition1
+ ", sum2: " + partition2);
}
Above solution will work for finding partitions with sum S and with any number of elements.
Hope this helps.
1. Divide by zero can be handled as a special case
2. Hashing floating is straightforward. why would it break if Double(0.00001).hashCode() != Double(0.0000100001).hashCode()?
Trie!
- HauntedGhost March 13, 2013Input location (x,y) can be different than the world cities locations. :P
- HauntedGhost March 11, 2013I gave the idea, i did not write the full code. We can handle ALL zero edge case seperately or by maintaining a flag inside the existing loop.
- HauntedGhost March 10, 2013no! because while adding you check if sum < 0 if yes then you start a new subarray.
But here, if even if product is < 0 it can become maximum if you multiply it with a negative number. See my solution above.
Maintain two variables maxProd, minProd.
maxProdOverall = maxProd, minProd = 1;
if(a[i] > 0)
{
maxProd = maxProd * a[i];
minProd = min(a[i]*minProd, 1);
}
else if(a[i] == 0)
{
maxProd = minProd = 1;
}
else
{
int temp = maxProd;
maxProd = max(minProd*a[i], maxProd);
minProd = min(temp*a[i], minProd);
}
maxProdOverall = max( maxProdOverall, maxProd );
I wrote code for this problem using KDTree, you can read the theory of KD Tree in wikipedia. Here is the implementation:
int compare(point p1, point p2, bool divX)
{
if(divX)
return (p1.x < p2.x)?-1:((p1.x>p2.x)?1:0);
else
return (p1.y < p2.y)?-1:((p1.y>p2.y)?1:0);
}
int partition(point *p, int s, int e, int pivot, bool divX)
{
swap(p[pivot], p[s]);
pivot = s;
while(s <= e)
{
while(s <= e && compare(p[s], p[pivot], divX) <= 0) s++;
while(s <= e && compare(p[e], p[pivot], divX) >= 0) e--;
if(s < e) swap(p[s], p[e]);
}
swap(p[pivot], p[e]);
return s-1;
}
// amortized O(n) method to find the nth element(0-based) in an array
int nthElement(point *p, int s, int e, int n, bool divX)
{
if(s == e) return s;
// get a random index between [s,e] inclusive
int RND = s + rand()%(e-s+1);
int pivot = partition(p, s, e, RND, divX);
int k = pivot - s;
if(n < k){
return nthElement(p, s, pivot-1, n, divX); // go left
}
if(n > k){
return nthElement(p, pivot+1, e, n-k-1, divX); // go right
}
return pivot;
}
// build the KD tree
// third parameter is for the division dimension
void build(point *p, int s, int e, bool divX)
{
if(s>=e) return;
// we will try to find the median of p[s..e]
int mid = (e+s)/2;
int n = mid - s; // we are interested in the median
nthElement(p, s, e, n, divX);
build(p, s, mid-1, !divX);
build(p, mid+1, e, !divX);
}
long bestDist = 1<<30;
int bestNode = -1;
void findNearestNeighbour(point *p, int s, int e, int x, int y, bool divX)
{
if(s >= e) return;
int mid = (e+s)/2;
point midp = p[mid];
long dx = x - midp.x;
long dy = y - midp.y;
long d = dx*dx + dy*dy;
if(bestDist > d)
{
bestDist = d;
bestNode = mid;
}
int s1 = s, e1 = mid-1;
int s2 = mid+1, e2 = e;
long delta = divX?dx:dy;
if(delta > 0)
{
swap(s1, s2);
swap(e1, e1);
}
findNearestNeighbour(p, s1, e1, x, y, !divX);
long delta2 = delta*delta;
if( delta2 < bestDist )
findNearestNeighbour(p, s2, e2, x, y, !divX);
}
Usage:
You need to first build the kd tree. Above method builds the tree in the array itself, it uses the quicksort partition algorithm to keep the tree balanced with max O(logn) height. This ensures that the query execution will tak O(logn).
// build the tree
build(points, 0, n-1, true); // n no. of points, true means we start with splitting by x-axis
// how to query the tree
findNearestNeighbour(points, 0, n-1, x, y, true);
// here (x,y) is the input point
Preprocessing is allowed, you can sort them, build kd tree or whatever you want. But you need to minimize the query execution time. Since it is an interview question, I'm guessing interviewer wouldn't be looking for complex solution like Voronoi diagram.
- HauntedGhost March 10, 2013Write a method to get the next string in the alphabetic order from the current string:
string next(string s){
int idx = s.size()-1;
s[idx]++;
while(s[idx] > 'z'){
s[idx] = 'a';
idx--;
if(idx == -1)
return 'a' + s;
else
s[idx]++;
}
return s;
}
From here it is simple, start with first 6-letters string "aaaaaa" and then keep generating strings using the above method and check if they are valid using isValid(s). If yes, print them, else do not print.
- HauntedGhost March 10, 2013O(n) is simple. they needed something better.
- HauntedGhost March 10, 2013O(n) is simple. they needed something better.
- HauntedGhost March 10, 2013heapify using which key? x coordinate or y? or are you going to calculate distance from all the numbers?
- HauntedGhost March 09, 2013// above solution was using DFS, but since we have a constraint on method parameters.
// I wrote this solution using BFS
void sum(node *root)
{
queue<node *> q;
q.push(root); // push the first node in the queue
// these counts will help in discriminating between the levels
int currentNodes = 1, childNodes = 0;
while(!q.empty()){
// get the front node from the queue
node *t = q.front();
q.pop(); // pop it out
currentNodes -= 1; // decrease the currentNodes count
t->val = 0;
if(t->left) {
// if left child is not NULL, we add this value to the current node's val
t->val += t->left->val;
q.push(t->left); // push it in the queue
childNodes += 1; // increase the childNodes by one
}
if(t->right) {
t->val += t->right->val; // same here, add the value to the t->val
q.push(t->right);
childNodes += 1;
}
// this means that we finished the current level,
// now it's time to go down to the next level.
// so we switch the counts now and make childNodes count again 0
if(currentNodes == 0){
currentNodes = childNodes;
childNodes = 0;
}
}
}
ohh! then we must use BFS.
- HauntedGhost March 09, 2013Do a postorder also maintain a level, if level is odd then add the root->val otherwise subtract it.
int sum(node *root, int level){
if(root == NULL) return 0;
int left = sum(root->left, level+1);
int right = sum(root->right, level+1);
if(level%2 == 0)
return left + right - root->val;
else
return left + right + root->val;
}
Working code available at: ideone.com/X2QIIR
- HauntedGhost March 09, 2013Keep track of minimum from left to right and take the difference with the current stock[i]. If it is greater than maxprofit, then update the maxprofit. Repeat it with all the stock values while going from left to right.
int getMaxProfit(int *a, int n)
{
int maxProfit = 0;
int minStockSoFar = a[0];
for(int i=1; i<n; i++)
{
maxProfit = max( maxProfit, a[i] - minStockSoFar );
minStockSoFar = min( minStockSoFar, a[i] );
}
return maxProfit;
}
Time complexity: O(n)
Space : O(1)
Sytax error: can not find symbol 'psvm'
A process provides the resources needed to execute a program. A process has a virtual address space, executable code, etc. Each process is started with a single thread, often called the primary thread, but can create additional threads from any of its threads.
A thread is an entity within a process. All threads of a process share the same virtual address space and system resources.
Hashcode is generated using hashfunctions. We have different hash functions available, you can simply wiki about it.
Hash functions generate a hash key, we use that hash key as an index to store data in the hash table. But what if two objects have same hash values?
To solve this, one way is to create chain of pointers in one bucket.
Suppose you have three values v1, v2, v3.
Hash values are : h(v1) = 0, h(v2)=1, h(v3) = 0
Hash Table:
[0] -> v1 -> v3
[1] -> v1
This solution works fine for less number of collisions, but when number of collisions grow high, the search starts taking ~ O(n)
Another solution is, Open Addressing:
In this method, if some collision occurs, then instead of making a chain in the bucket, we find next available location in the same hash table, and then we store our value there.
For the example above:
[0] -> v1
[1] -> v2
[2] -> v3
We also have different type of methods to search next available position in the hash table.
1. Linear Probing: if the hash value is h and it collides then check at h+1
2. Quadratic Probing: if the hash value is h and it collides then increase the hash by 1^2, 2^2 , 3^2 and so on.
I think this should suffice.
We need to consider only odd level depths. if we return 0 for even levels. then
max( left, right ) will always be either 0 (if both the child subtree leaves are at even depth) or the actual odd depth.
0 is the minimum number I could think of, you can return INT_MIN as well if you want. It is used just to skip the even depths.
ideone.com/rDwrm8 - code link
- HauntedGhost March 06, 2013You can use bit operators, here is how I would do it:
for( int i =0 ; i < 1<<n; i++) { // iterate through all possible combinations
cout<<"{";
for(int j = 0 ; j<n; j++) {
if( (i&(1<<j)) > 0 ) {
cout<<a[j]<<",";
}
}
cout<<"}, ";
}
I am generating all the possible bit values till n 0, 1, 00, 01, 10, 11 and so on. Then i run another loop and pick only those number whose index bits are set.
- HauntedGhost March 06, 2013This is simple brute force technique. It will take O(n*L) where n = size of "str" and L = size of "find"
- HauntedGhost March 05, 2013If space is no issue, you can use suffix tree. Time complexity: O(query length)
Or you can use KMP algorithm it requires lesser space than suffix tree.
I think this should work, not tested though:
node *findLastNth(node *head, int n){
node *temp = head;
while(temp != NULL && n--) temp = temp->next;
if(temp == NULL) return NULL;
while(temp){
temp = temp->next;
head = head->next;
}
return head;
}
@Loler, You are right, my bad. It's O(nk)
- HauntedGhost March 05, 2013@Loler. Check mine
- HauntedGhost March 05, 2013We can do it in O(n^2) using Dynamic Programming, this code is only for positive integers, we can tweak it to take care of -ve integers as well:
// idea is
// a sum x is possible if for any i x-a[i] is possible
bool subsetsum(int *a, int n, int k){
int *s = new int[k+1];
for(int i=0; i<k+1; i++) s[i] = 0;
s[0] = 1;
for(int i=0; i<n; i++)
for(int j=k; j>=a[i]; j--)
s[j] |= s[j-a[i]];
return s[k];
}
You can test the code using your custom test case @ ideone.com/Zsw3J4
- HauntedGhost March 05, 2013Position of a given letter 'w' in the matrix will be:
int i = (w-'a')/5;
int j = (w-'a')%5;
Get the difference of current 'i' and new 'i' calculated using above formula,
int diff_i = (new_i - old_i);
int diff_j = (new_j - old_j);
From here it's simple,
if(diff_i < 0)
// append 'U' in the output (diff_i) times
else
// append 'D' in the output (diff_i) times
// same with j
if(diff_j < 0)
// append 'L' in the output (diff_j) times
else
// append 'R' in the output (diff_j) times
Interviewers generally seek solutions without global and reference variables! Because it may lead to concurrency issues in a multi-threaded system.
- HauntedGhost March 04, 2013How come 6009 upside down is 6009? :P
I think it is 9006!
Out of 10 digits, we have only 3 digits which look the same as they are upside down.
So, for 1 digit number, probability of getting a digit which will look same after flipping it upside down is = 3/10
Now, for n digits we have n independent events:
so the total probability for n digits:
P = (3/10)^n
For n = 2, P = (3*3)/(10*10) = 3/50 = 0.06
Correct me if I'm wrong.
This is quite very big question to be asked in an interview.
Anyways, I'm giving you a rough idea. We need to keep one thing in mind while generating the maze, there must be a path in and out of the maze! so that it could be solved.
We represent a maze as a double dimension of integer values:
int maze[rows][cols];
We use only four bits of an integer in this 2D array. Each four bits represents the boundary presence at cel [i,j].
For example:
if maze[0][0] = 2; (i.e. 0010) it means west boundary of the cell is blocked, and east, west, south boundaries are open. (bit from left to right are in order east-north-west-south)
and if maze[0][0] = 3 (ie. 0011) it means west and south are blocked
Now, while generating the maze we need to enforce a condition that, if a wall in a cell is open then its opposite wall should also be open in order to have a valid path.
We can do it using:
enum DIR {
E(1<<0),N(1<<1),W(1<<2),S(1<<3)
int bit;
private DIR(int bit)
{
this.bit = bit;
}
int getBit(){
return this.bit;
}
};
DIR opposite(DIR d) {
if(d == DIR.E) return DIR.W;
if(d == DIR.N) return DIR.S;
if(d == DIR.S) return DIR.N;
if(d == DIR.W) return DIR.E;
}
Code for generating the maze:
int [][]getMaze(int rows, cols){
DIR dirs[4] = {DIR.N, DIR.E, DIR.W, DIR.S};
Collections.shuffle(Arrays.asList(dirs));
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
Collections.shuffle(Arrays.asList(dirs));
for(DIR d: dirs){
maze[i][j] |= d.getBit();
maze[i][j] |= opposite(d).getBit();
}
}
}
}
This should do the job.
The second part of the question is easy. Use a simple DFS with backtracking.
Thanks!! :)
- HauntedGhost March 04, 2013We do not need to pick alternate depths. Suppose tree has 5 leaves, which are at level {1,3,5,2,4} respectively.
I'm returning the level only if the level is odd otherwise returning zero. Which would ensure the final depth to the deepest odd leveled leaf depth. :)
I think it's simple, you can recursively solve this problem. I'd break down it in two phases:
1. when we go down the tree recursively, maintain a variable "level" which will store the current node level in the tree.
getDeepestOdd(root->left, level+1); // go left
getDeepestOdd(root->right, level+1); // go right
2. after 1st step, we will hit the leaves of the tree, if it is a leaf and level is odd return the level, else return 0
if(root->left == NULL && root->right == NULL) {
if(level%2 == 0) return 0;
else return level;
}
3. while coming from bottom to top take the max from both left and right subtree
return max(getDeepestOdd(root->left, level+1),
getDeepestOdd(root->right, level+1));
Full Code:
int getDeepestOdd(node *root, int level){
if(root == NULL) return 0;
// if we encounter a leaf
if(root->left == NULL && root->right == NULL) {
if(level%2 == 0) return 0; // if even level, return 0
else return level; // else return the level
}
return max(getDeepestOdd(root->left, level+1),
getDeepestOdd(root->right, level+1));
}
If you want, you can run the code on ideone @ ideone.com/0k45Ed
- HauntedGhost March 04, 2013Thanks! Yeah i mistakenly put left call first. the method i actually wrote is for finding k-smallest number. :)
- HauntedGhost March 04, 2013As everybody has figured out we can solve it in O(n) using inorder:
node *kthLargest(node *root, int &k){
if(root == NULL)
return NULL;
node *n = kthLargest(root->left, k);
if(n != NULL) return n;
k -=1;
if(k == 0) return root;
n = kthLargest(root->right, k);
return n;
}
But, if we are allowed to modify the tree node, we can add "size" integer member in it and then sizeify the tree. root->size = size of the subtree rooted at root.
Here is a code snippet to calculate the size of all the possible subtrees:
int sizeifyBST(node *&root){
if(root == NULL){
return 0;
}
int leftsize = sizeifyBST(root->left);
int rightsize = sizeifyBST(root->right);
return root->size = leftsize + rightsize + 1;
}
Now, we can easily find kth largest in O(logn):
suppose we are at node T:
1. k == size of the left subtree + 1, then return T
2. if k > size of the left subtree + 1, then recursively call the same method with k = k - size of the left subtree
3. if k < size of the left subtree, then go left with same k
node *findKthLargestFaster(node *root, int k){
if(root == NULL) return NULL;
int leftsubtreesize = root->size
- (root->right?root->right->size:0)
- 1;
if(k == leftsubtreesize + 1)
return root;
else if(k < leftsubtreesize + 1)
return findKthLargestFaster(root->left, k);
else
return findKthLargestFaster(root->right, k - leftsubtreesize-1);
}
Here is the link to the working code, if you guys are interested:
ideone.com/Qkkkl6
Link to run the code: ideone.com/9ttqJt
int di[] = {0,1,1};
int dj[] = {1,1,0};
bool findStr(vector<string> s, int i, int j, string tofind, int l){
int r = s.size();
int c = s[0].size();
if(l == tofind.size()) return true;
if(i >= r || j >= c) return false;
bool ret = false;
if(tofind[l] == s[i][j]){
for(int d=0; d<3; d++){
ret |= findStr(s, i+di[d], j+dj[d], tofind, l+1);
}
}
else{
for(int d=0; d<3; d++){
ret |= findStr(s, i+di[d], j+dj[d], tofind, 0);
}
}
return ret;
}
// Using only one queue and without any marker.
void print(node *root){
queue<node *> q;
q.push(root);
int parent_nodes = 1;
int child_nodes = 0;
while(!q.empty()){
node *t = q.front();
q.pop();
parent_nodes -= 1;
cout<<t->val<<" ";
if(t->left) {
q.push(t->left);
child_nodes += 1;
}
if(t->right) {
q.push(t->right);
child_nodes += 1;
}
if(parent_nodes == 0){
cout<<"\n";
parent_nodes = child_nodes;
child_nodes = 0;
}
}
}
int GCD(int a, int b){
if(b==0) return a;
return GCD(b, a%b);
}
int LCM(int a, int b){
return a*b/GCD(a,b);
}
int LCM2(int *a, int i, int n){
if(i == n){
return 1;
}
return LCM(a[i],LCM2(a,i+1,n));
}
int a[] = {3,5,2};
LCM2(a,0,3) will be the call.
Output :
- HauntedGhost September 22, 2015