tryingtosolvemystery
BAN USER- 1of 3 votes
AnswersGiven 2 binary arrays A and B i.e. containing only 0s and 1s each of size N.
- tryingtosolvemystery in India
Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum possible value.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersHow would you weigh an aeroplane
- tryingtosolvemystery in United States| Report Duplicate | Flag | PURGE
Goldman Sachs Financial Software Developer Brain Teasers - 0of 0 votes
AnswersThere is a stream of numbers coming in and you have to find K largest numbers out of the numbers received so far at any given time. Next problem is that a constraint is added. memory is limited to m. m < k. How would you achieve the goal still.
- tryingtosolvemystery in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswersGiven a floor in a building, we need to place tiles on it.
- tryingtosolvemystery in United States
*You can use tiles of a given set of dimensions*. But each type of the tile has a given cost associated. (you cannot cut a tile). How would you tile the floor in minimum cost ? Also answer whether the floor can be tiled at all or not ?| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
Whichever city has the game, for each of its edge calculate the population of that sub-graph (doing a DFS or BFS) and return the max of all those sub-graphs. O(n)
- tryingtosolvemystery September 15, 2016public static void Permutations(string prefix, int n, bool bUsedEarlier, bool cExhaustedEarlier, ref int count)
{
char[] chars = { 'a', 'b', 'c' };
if (n == 0)
{
Console.WriteLine(prefix);
count++;
return;
}
foreach (var @char in chars)
{
if (@char == 'b' && bUsedEarlier)
continue;
if (@char == 'c' && cExhaustedEarlier)
continue;
var bUsed = bUsedEarlier || @char == 'b';
var cExhausted = cExhaustedEarlier || prefix.Length > 0 && prefix[prefix.Length - 1] == 'c' && @char == 'c';
Permutations(prefix + @char, n - 1, bUsed, cExhausted, ref count);
}
}
public static void StringTest()
{
int count = 0;
Permutations("", 4, false, false, ref count);
Console.WriteLine("Count of Permutations: " + count);
}
Optimal solution for this is O(N)...
Basically we can try to classify problems such that kind of approach and complexity can be identified quickly first. Anyone wana share their ideas on the usual approaches you follow while problem solving ?
What is the value in cumulative array for (1,n-1). arent the values cumulated from 0 index ?
- tryingtosolvemystery August 07, 2013It is NP complete if tiles are limited in number, if unlimited then DP can be used.
- tryingtosolvemystery August 07, 2013void printAllSubsets(int[] a, int j, int n, string set)
{
if(j == n)
print(set + " "); // add a space at end demarcating end of 1 subset
for(int i = j;i < n;j++)
{
// 2options at each element. either it is part of this subset or not
printAllSubsets(a,i+1,n, set+a[i].ToString());
printAllSubsets(a,i+1,n, set);
}
}
int main()
{
int[] a = new int[] {1,4,5,67,4,3};
printAllSubsets(a,0,arr.Length, "");
}
Paging memory or space means the amount of space to be allocated on the HDD which is used to swap out from main memory. This is usually done to make better use/distribution of available limited main memory amongst multiple processes. So that every process which usually can address 2GB (32-bit) or if PAE then 3GB of user space virtually can access that space, though all of it if allcoated may not be present in main memory but partly in the persistent store i.e. HDD.
- tryingtosolvemystery August 06, 2013How would you do external merge sort with 'm' memory < N * m . What is the overall complexity of your solution to query the top K numbers at any time ?
- tryingtosolvemystery August 06, 2013We have to find min first and a max after such that max - min = maxprofit .This can be done in O(n). while traversing start with first price as min, keep going forward , if you find a lower number then update min. If you find higher number than min, update max and maxprofit using curent min and max. whenever u find a new min after a max has been identified then update the min and reset the max. repeat. always update maxprofit any better poitns are found. this should work for all cases . (assuming prices are not -ve ofcourse)
case of 15,25,10,30. ans shud be 10,30
O(n) simple in-order traversal with conditions solution
}
- tryingtosolvemystery September 15, 2016