Raul Rivero
BAN USERJavascript solution:
function reorderArray() {
return indices.map(function (val, i) {
return array[indices.indexOf(i)];
});
}
There's no need of DP approach, we can solve this in O(n) time and O(1) complexity!
public int MaxRobbingVal(int[] values)
{
int n = values.Length;
if (n == 0)
return 0;
int sum1 = values[0], sum2 = 0, sum_aux = 0;
for (int i = 1; i < n; i++)
{
sum_aux = Math.Max(sum1, sum2);
sum1 = sum2 + values[i];
sum2 = sum_aux;
}
return Math.Max(sum1, sum2);
}
I forgot to put some test cases like:
incorrect numbers: "-.15", "12.3-", "4fe", ".15", "15.", "15-", "1-5" // return false
correct numbers: "154", "-23", "15.36", "-1.25" // return true
This is my C# solution to the problem, unfortunately I couldn't be able to write it on time due to my nerves! Best of luck guys!
public static bool IsNumber(string number)
{
int n = number.Length, dots = 0;
if (number[0] == '.' || number[n - 1] == '.' || number[n - 1] == '-')
return false;
if ((number[0] < 48 || number[0] > 57) && number[0] != '-')
return false;
for (var i = 1; i < n; i++)
{
if (dots > 1)
return false;
if (number[i] < 48 || number[i] > 57)
{
if (number[i] == '.')
{
if (i == 1 && number[0] == '-')
return false;
else
dots++;
}
else
return false;
}
}
return true;
}
C# solution using Manacher's algorithm O(n)
public static string preProcess(string s)
{
int n = s.Length;
if (n == 0)
return "^$";
string ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.Substring(i, 1);
ret += "#$";
return ret;
}
public static string LPS(string s)
{
string T = preProcess(s);
int n = T.Length;
int[]P = new int[n];
int C = 0,
R = 0;
for (int i = 1; i < n - 1; i++)
{
int i_mirror = 2 * C - i; // equals to i' = C - (i-C)
P[i] = (R > i) ? Math.Min(R - i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++)
{
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
return s.Substring((centerIndex - 1 - maxLen) / 2, maxLen);
}
You're right, that's the best approach to this problem!
- Raul Rivero September 02, 2014That definitely is not an Amazon interview question, for sure, too simple!
- Raul Rivero August 29, 2014Yes, I know, but either way we cannot use binary search since the array is not completely sorted. So what would be the best approach to this problem? Please guys, don't just publish the code, but also the logic. Thanks
- Raul Rivero August 28, 2014If the number we're looking for has duplicates, should we return its first occurrence? If so, first thing we need to do is select the correct data structure for this problem, if the array wouldn't be rotated, just sorted, everyone could get to the answer quickly: binary search, that's it. But that's not the case, for this problem I think all we need is a Hash Table, which allows us to find an element very quick, and so its index.
- Raul Rivero August 27, 2014
Repallisonepollard, Applications Developer at Accenture
I am Allison from Germantown. I work as a Staff manager at The LawnGuru company. But my interest in blogging ...
Javascript code:
- Raul Rivero March 16, 2016