__coder
BAN USER- 0of 0 votes
AnswersYou have coins with different denominations and you have limited number of each denominations (some maybe zero), how will you determine if you can supply the given change. DP , are you sure? think again.
- __coder in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
A basic recursive function: Gool is to reach desired lenght for open paranthesis number and zero our closed paranthesis. As you add open paranthesis both increment open and close paranthesis number and call again, next step if you have any close paranthesis call recursive again this time decrementing close paranthesis number.
- __coder November 16, 2011using System;
using System.Collections.Generic;
using System.Text;
namespace CSharp
{
public class Class1
{
public static void Main(string[] args)
{
StringBuilder b = new StringBuilder();
print(0,0,3,b);
}
static void print (int o, int c, int l, StringBuilder b)
{
if(o==l)
{
if(c>0)
{
b.Append(")");
print(o,c-1,l,b);
b.Remove(b.Length-1,1);
}
else
System.Console.WriteLine(b.ToString());
}
else
{
b.Append("(");
print(o+1,c+1,l,b);
b.Remove(b.Length-1,1);
if(c>0)
{
b.Append(")");
print(o,c-1,l,b);
b.Remove(b.Length-1,1);
}
}
}
}
}
worst algorithm is n2. If you sort by start times (nlogn)
then for each app(current app), do a binary search to find the largest start time (last conflicting app) which is less than current apps end time. All the apps between current app and last conflicting app is conflicting. so nlogn+nlogn
Repamysamson688, Accountant
Hi, I am an art teacher, good in all areas of art history, from ancient art through to contemporary art ...
Repethelynfrose, Computer Scientist at 247quickbookshelp
Hello, I am Ethelyn and I live in Lake Worth, USA. I am working as a Dog Trainer and Dog ...
Reprachelwrosa1, Computer Scientist at ABC TECH SUPPORT
Hello, I am Rachel and I live in Charleston, USA. I am working as a data entry clerk who is ...
:) JuggerNuts, i will leave it to you to discover why this algo will find the conflicting apps that start earlier than current app. if you can not find. let me know and i will explain. good luck.
- __coder November 30, 2011