CareerCup

Hint : Think binary search for the answer.

If you had a function bool isPossible which could tell you if its possible to paint the boards in time T or less.

Keep assigning boards to painter greedily till the time taken < mid. If you run out of painters, isPossible = false.
else isPossible = true.

public int paint(int A, int B, ArrayList<Integer> C) {
	    
	    long res = Long.MAX_VALUE;
	    long low = 0;
	    long high = Long.MAX_VALUE;
	    long mid;
	    
	    while (low <= high) {
	        
	        mid = low + ((high - low) >> 1);
	        
	        boolean status = possible(A, B, C, mid);
	        
	        if (status) {
	            res = mid;
	            high = mid - 1;
	        } else {
	            low = mid + 1;
	        }
	    }
	    
	    
	    return (int) (res);
	    
	}
	
	private boolean possible(int A, int B, ArrayList<Integer> C, long time) {
	    
	    int n = C.size();
	    int index = 0;
	    long total;
	    
	    for (int i = 0; i < A && index < n; i++) {
	        
	        total = 0;
	        
	        while (total < time && index < n) {
	            total += (1L * C.get(index) * B);
	            if (total > time)
	                break;
	            index++;
	        }
	    }
	    
	    if (index != n)
	        return false;
	    
	    return true;
	}

Create a directed graph and apply Topological Sorting.

It is quite clear in the question that number of teams and track length is input to the function. So, you can take any value for input parameters.

Thanks Sumit.

Please download and use the app and encourage others too. Also give your valuable suggestions and feedback for the app.

Sadly, no....but i will try to learn iOS development first.

Test

Take XOR of all the numbers of array. Resulting number in XOR is the answer.

void merge(int a[], int begin, int n) {
	int p1 = begin;
	int p2 = begin + n;
	int b = a[p2];
	for(int i = p2-1; i > p1; i--) {
		a[i+1] = a[i];
	}
	a[begin + 1] = b;
	merge(a, begin + 3, n-1);
}

It seems to be subset-sum problem.

Find a subset with sum of elements half of total sum of array.

1.) Sort the array.
2.) Starting from second element, swap 2nd and 3rd element, 4th and 5th element and so on.

For getting holes info, you need to look at each point. So the best solution is O(n^2). DFS will give O(n^2) only.

Any new approach is welcome.

It was asked in Amazon Ninja Coder 2013.

Please refrain from posting questions for ongoing competition.

Now the competition is over. I will answer this.

I used recursive approach to solve this.

First mark the matrix with barren land as 0 and holes as 1.
Then check recursively for holes using DFS.

Let me know if you guys want working code.

I think anotherguy's algo is correct.
@anonymous - Below is solution for your test case .

l = {0,4,4,6,6,6,6,6,6,6}
r = {6,6,6,6,6,6,6,6,6,0}

ans = {0,3,0,2,5,0,3,5,2,0}

Total water stored = 15

This question was asked in Topcoder SRM 592

ya

I think this problem is not asked by FB, but it is asked in Illuminati Hiring Challenge that ended today on HackerRank.com. Only the words have been changed, problem seems to be exactly what was asked there.

void braces(int open, int close, string str) {
        if(open == 0 && close == 0) {
                 cout << str << endl;
        }
        if(open > 0) {
                 braces(open-1, close+1, str + "{");
        }
        if(close > 0) {
                 braces(open, close-1, str + "}");
        }
}

int main() {
      int n;
      cout << "Please enter number of braces : ";
      cin >> n;
      int open = n, close = 0;
      braces(open, close, "{");
      return 0;
}

@anish[1] - Yes you can start from anywhere. When did I said that you have to start from middle ?

You have to fill whole matrix with L shaped blocks such that only that cell remains unfilled whose co-ordinate is given.

It was asked to me in second face to face.

What is absurd in question ?

No its not knight movement because knight goes 2 step forward then 1 step left or right.

Here its one step forward and then 1 step left or right.

I gave divide and conquer solution. But I don't think divide and conquer is correct.
For Ex. In the last recursive call we will have 2 X 2 matrix where we can fill only 3 block, which is not correct as we have to fill all blocks except i,j

There must be some DP solution.

You are only taking a case where all negative numbers come first followed by 0 and positive numbers, while in question it is not mentioned. So, array can have negative and positive numbers dispersed randomly.

Geet :- DLL means doubly linked list. What you are saying will be true for circular doubly linked list.

In DLL, previous pointer of first node points to null. While in circular DLL it points to tail.

So you have traverse all along the way to tail.

As this is binary tree, so we have to sort array in descending order and treat this array like we have stored max-heap. So this will be complete binary tree which is left aligned.
Then calculate tree weight.

It is simple

If the question really asks for intersection of lines (as line extends to infinity both ways), then we just have to compare their slope. If slope is equal they will never intersect aka parallel otherwise they will overlap at some point.

But, I think question would be for intersection of line segment (both endpoints of line segment are fixed).

This can be done in O(n). Will post my algo, when I will be free.

I could not understand why will you pick 'a' as it is not present in input string 'bcd' ?

Min Coin Problem

int findMaxSum(int arr[], int n)
{
	int incl = arr[0];
	int excl, excl_new;
	for(int i = 1; i < n; i++)
	{
		excl_new = incl > excl ? incl : excl;
		incl = excl + arr[i];
		excl = excl_new;
	}
	return (incl > excl ? incl : excl);
}

How can you say that doubling floors each time is optimal solution ??

We can triple floors each time also...

For finite floors we can do load balancing as you have described...
but for infinite floors how can we do load balancing ?

what will be the optimized number of throws??

Its a 0-1 knapsack problem. We have to minimize number of people given a total number of followers.

// Program to find the amount of water in jth glass of ith row
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// Returns the amount of water in jth glass of ith row
float findWater(int i, int j, float X)
{
    // A row number i has maximum i columns. So input column number must
    // be less than i
    if (j > i)
    {
        printf("Incorrect Input\n");
        exit(0);
    }
 
    // There will be i*(i+1)/2 glasses till ith row (including ith row)
    float glass[i * (i + 1) / 2];
 
    // Initialize all glasses as empty
    memset(glass, 0, sizeof(glass));
 
    // Put all water in first glass
    int index = 0;
    glass[index] = X;
 
    // Now let the water flow to the downward glassses till the
    // amount of water X is not 0 and row number is less than or
    // equal to i (given row)
    for (int row = 1; row <= i && X !=0.0; ++row)
    {
        // Fill glasses in a given row. Number of columns in a row
        // is equal to row number
        for (int col = 1; col <= row; ++col, ++index)
        {
            // Get the water from current glass
            X = glass[index];
 
            // Keep the amount less than or equal to
            // capacity in current glass
            glass[index] = (X >= 1.0f) ? 1.0f : X;
 
            // Get the remaining amount
            X = (X >= 1.0f) ? (X - 1) : 0.0f;
 
            // Distribute the remaining amount to the down two glasses
            glass[index + row] += X / 2;
            glass[index + row + 1] += X / 2;
        }
    }
 
    // The index of jth glass in ith row will be i*(i-1)/2 + j - 1
    return glass[i*(i-1)/2 + j - 1];
}
 
// Driver program to test above function
int main()
{
    int i = 2, j = 2;
    float X = 2.0; // Total amount of water
 
    printf("Amount of water in jth glass of ith row is: %f",
            findWater(i, j, X));
 
    return 0;
}

They are asking for maximum path not minimum path.

typedef unordered_map<Node *, Node *> Map;
 
Node *clone(Node *graph) {
    if (!graph) return NULL;
 
    Map map;
    queue<Node *> q;
    q.push(graph);
 
    Node *graphCopy = new Node();
    map[graph] = graphCopy;
 
    while (!q.empty()) {
        Node *node = q.front();
        q.pop();
        int n = node->neighbors.size();
        for (int i = 0; i < n; i++) {
            Node *neighbor = node->neighbors[i];
            // no copy exists
            if (map.find(neighbor) == map.end()) {
                Node *p = new Node();
                map[node]->neighbors.push_back(p);
                map[neighbor] = p;
                q.push(neighbor);
            } else {     // a copy already exists
                map[node]->neighbors.push_back(map[neighbor]);
            }
        }
    }
 
    return graphCopy;
}

HackerRank ongoing challenge question.

We can solve this using Dynamic Programming which will take O(n^2) space and will have time complexity of O(n^2) where n is length of string.

However, it can be solved without Dynamic Programming. So, time complexity will be O(n^2) but in constant space.

int longestPalindromicSubstring(char* str)
{
	int len = strlen(str);
	int maxLength = 1;
	int start = 0;
	int low, high;
	
	for(int i = 1; i < len; i++)
	{
		// Find longest even length palindrome with
		// center points as i-1 and i
		low = i-1;
		high = i;
		while(low >= 0 && high < len && str[low] == str[high])
		{
			if(high - low + 1 > maxLength)
			{
				start = low;
				maxLength = high - low + 1;
			}
			low--;
			high++;
		}
		
		// Find longest odd length palindrom with
		// center point as i
		low = i-1;
		high = i+1;
		while(low >= 0 && high < len && str[low] == str[high])
		{
			if(high - low + 1 > maxLength)
			{
				start = low;
				maxLength = high - low + 1;
			}
			low--;
			high++;
		}
	}
	
	printf("Longest Palindromic Substring is: ");
	for(int i = start; i <= start + maxLength - 1; i++)
	{
		printf("%c", str[i]);
	}
	
	return maxLength;
}

Method 1 - Simple but Inefficient. Time Complexity is O(n^2)

Start from root and do an inorder traversal of the tree. For each node N, check whether the subtree rooted with N is BST or not. If BST, then return size of the subtree rooted with N. Else, recur down the left and right subtrees and return the maximum of values returned by left and right subtrees.

int largestBST(struct node *root)
{
   if (isBST(root))
     return size(root);
   else
    return max(largestBST(root->left), largestBST(root->right));
}

Method 2 - Efficient

Traverse tree in bottom up manner and pass information like size of BST if it is BST when you recurse back.

/* Returns size of the largest BST subtree in a Binary Tree
  (efficient version). */
int largestBST(struct node* node)
{
  // Set the initial values for calling largestBSTUtil()
  int min = INT_MAX;  // For minimum value in right subtree
  int max = INT_MIN;  // For maximum value in left subtree
 
  int max_size = 0;  // For size of the largest BST
  bool is_bst = 0;
 
  largestBSTUtil(node, &min, &max, &max_size, &is_bst);
 
  return max_size;
}
 
/* largestBSTUtil() updates *max_size_ref for the size of the largest BST
   subtree.   Also, if the tree rooted with node is non-empty and a BST,
   then returns size of the tree. Otherwise returns 0.*/
int largestBSTUtil(struct node* node, int *min_ref, int *max_ref,
                            int *max_size_ref, bool *is_bst_ref)
{
 
  /* Base Case */
  if (node == NULL)
  {
     *is_bst_ref = 1; // An empty tree is BST
     return 0;    // Size of the BST is 0
  }
 
  int min = INT_MAX;
 
  /* A flag variable for left subtree property
     i.e., max(root->left) < root->data */
  bool left_flag = false;
 
  /* A flag variable for right subtree property
     i.e., min(root->right) > root->data */
  bool right_flag = false;
 
  int ls, rs; // To store sizes of left and right subtrees
 
  /* Following tasks are done by recursive call for left subtree
    a) Get the maximum value in left subtree (Stored in *max_ref)
    b) Check whether Left Subtree is BST or not (Stored in *is_bst_ref)
    c) Get the size of maximum size BST in left subtree (updates *max_size) */
  *max_ref = INT_MIN;
  ls = largestBSTUtil(node->left, min_ref, max_ref, max_size_ref, is_bst_ref);
  if (*is_bst_ref == 1 && node->data > *max_ref)
     left_flag = true;
 
  /* Before updating *min_ref, store the min value in left subtree. So that we
     have the correct minimum value for this subtree */
  min = *min_ref;
 
  /* The following recursive call does similar (similar to left subtree)
    task for right subtree */
  *min_ref =  INT_MAX;
  rs = largestBSTUtil(node->right, min_ref, max_ref, max_size_ref, is_bst_ref);
  if (*is_bst_ref == 1 && node->data < *min_ref)
     right_flag = true;
 
  // Update min and max values for the parent recursive calls
  if (min < *min_ref)
     *min_ref = min;
  if (node->data < *min_ref) // For leaf nodes
     *min_ref = node->data;
  if (node->data > *max_ref)
     *max_ref = node->data;
 
  /* If both left and right subtrees are BST. And left and right
     subtree properties hold for this node, then this tree is BST.
     So return the size of this tree */
  if(left_flag && right_flag)
  {
     if (ls + rs + 1 > *max_size_ref)
         *max_size_ref = ls + rs + 1;
     return ls + rs + 1;
  }
  else
  {
    //Since this subtree is not BST, set is_bst flag for parent calls
     *is_bst_ref = 0;
     return 0;
  }
}

1.) Put all characters string2 in a stack.
2.) Then start traversing string1 in reverse order
2.1) If currect character matches with top of stack then pop it from stack.
3.) After traversing string1 fully, If stack is empty then return true else return false

I think BFS or DFS will work.

Anonymous (Question Poster) - How many years of experience you have??

use bit vector of 95000. He was looking for bit array at that time.

Yes, in case of all negative numbers we need special check here.

See my solution above.

Another very good approach

int maximumSum(int arr[])
{
	int size = sizeof(arr)/sizeof(arr[0]);
	int incl = arr[0];
	int excl = 0, excl_new;
	for(int i = 1; i < size; i++)
	{
		excl_new = incl > excl ? incl : excl;
		incl = excl + arr[i]; // sum including current element
		excl = excl_new; // sum excluding current element
	}
	return (incl > excl ? incl : excl);
}

Explain your code. What is temp? How it will be constructed?

As per your answer O(log n) + O(n) = O(n).

Mine is giving O(log n) because after finding index of key, I am again doing binary search on left part to find first occurrence. However, you are doing it linear search on the left part.

Your complexity will be O(n). It can be solved in O(log n)

int binarySearch(int arr[], int start, int end, int key)
{
	if(end < start) return -1;
	int mid = start + (end - start) / 2;
	if(arr[mid] == key)
	{
		int leftIndex = binarySearch(arr, start, mid - 1, key);
		return (leftIndex == -1 ? mid : leftIndex);
	}
	else if(arr[mid] > key)
	{
		return binarySearch(arr, start, mid - 1, key);
	}
	else
	{
		return binarySearch(arr, mid + 1, end, key);
	}
}

Your code will not give first occurrence of given number.