Amazon Interview Question
SDE-2sCountry: United States
Can be further improved using binary Search
public class BracketAnalysis
{
public class Brakets
{
public int NumberOfOpen { get; set; }
public int NumberOfClose { get; set; }
}
public int result { get; set; }
public void FindIndexOfEqualBrakets(string input)
{
for (var i = 1; i < input.Length; i++)
{
var obj = ReadString(input, 0, i);
var obj1 = ReadString(input, i, input.Length - 1);
if (obj.NumberOfOpen == obj1.NumberOfClose || obj.NumberOfClose == obj1.NumberOfOpen) { result = i; }
}
}
private Brakets ReadString(string input, int startIndex, int endIndex)
{
var obj = new Brakets();
for (var i = startIndex; i < endIndex; i++)
{
if (input[i] == '(')
{
obj.NumberOfOpen++;
}
else if (input[i] == ')')
obj.NumberOfClose++;
}
return obj;
}
}
Here is a recursive based solution
public static int FindMidDriver(string t)
{
return FindMid(t, 0, t.Length);
}
public static int FindMid(string t, int s, int e)
{
int i = s;
bool hasOpenBrace = false;
for (i = s; i <= e; i++)
{
if (t[i] == '(')
{
hasOpenBrace = true;
break;
}
}
bool hasCloseBrace = false;
int j = e;
for (j = e; j >= i; j--)
{
if (t[j] == ')')
{
hasCloseBrace = true;
break;
}
}
if (hasOpenBrace && hasCloseBrace)
{
return FindMid(t, i + 1, j - 1);
}
else if (hasOpenBrace)
{
return i;
}
else
{
return j + 1;
}
}
public class bracesstring {
public int findsolution(String str){
for(int i=0;i<str.length();i++){
if(findoccurences('(',str.substring(0, i))==findoccurences(')',str.substring(i)))
return i;
}
return str.length();
}
private int findoccurences(char c, String str) {
int m=0;
for(int i=0;i<str.length();i++){
if(c==str.charAt(i)){
m++;
continue;
}
}
return m;
}
}
k will always exist, 0<=k<=n
let's assume k was found at some position (denoted by |)
........|.....
now if a ( is added at the end, k remains the same since no. of )s on right half remain the same.
........|.....(
if a ) is added the end, then we have 1 extra ) on the right half, let's find the new k
if the immediate next bracket after the division (k+1 th bracket) was (, then sliding division partition by 1 position to the right balances the brackets again since no. of (s in left half also increases by 1 now.
........|(....) -> ........(|....)
if the immediate next bracket after the division (k+1 th bracket) was ), then sliding division partition by 1 position to the right balances the brackets again since no. of )s in right half also decreases by 1 now.
........|)....) -> ........)|....)
So, effectively if we have a given string and a k, appending a ) to the same string increases k by 1, appending ( to the same string doesn't change k.
Starting with an empty string, k = 0, start parsing the given string, for each ) ecnountered increase k by 1.
ans = no. of )s in the string
we can solve this problem using two arrays, which store the count of open brackets and close brackets till current point and based on these two arrays, it finds out the value of K
FindK(string brackets)
{
if(String.IsNullOrWhiteSpace(brackets))
{
return -1; // -1 when you don't find the value of K
}
var openBracketsArray = new int[brackets.Length];
var closeBracketsArray = new int[brackets.Length];
if(brackets[0] == '(')
{
openBracketsArray[0] = 1;
closeBracketsArray[0] = 0;
}
else
{
openBracketsArray[0] = 0;
closeBracketsArray[0] = 1;
}
for(int i = 1; i < brackets.Length; i++)
{
if(brackets[i] == '(')
{
openBracketsArray[i] = openBracketsArray[i-1] + 1;
closeBracketsArray[i] = closeBracketsArray[i-1];
}
else
{
openBracketsArray[i] = openBracketsArray[i-1];
closeBracketsArray[i] = closeBracketsArray[i-1] + 1;
}
}
if(closeBracketsArray[brackets.Length-1] == 0)
{
return 0;
}
for(int i = 0; i < brackets.Length; i++)
{
if(openBracketsArray[i] == closeBracketsArray[brackets.Length-1] - closeBracketsArray[i])
{
return i+1;
}
}
return -1;
}
Complexity of this algorithm is O(N) + O(N).
If we want to remove the space complexity, what we can do it that from each i (ranging from 0 to n-1), check if brackets[0, i] and brackets[i+1, n-1] satisfy the above condition.
but in this, the complexity goes to O(N*N) + O(1).
Count the number of open/close parenthesis
Index 0 1 2 3 0 1 2 3 4 5 6 0 1
( ( ) ) ( ( ) ) ) ) ( ( (
num Opened 1 2 2 2 1 2 2 2 2 2 3 1 2
num Closed 2 2 2 1 4 4 4 3 2 1 0 0 0
i+1 i i
public static int FindK(char[] a)
{
if (a == null || a.Length == 0)
return -1;
int numClose = 0;
foreach (var c in a)
{
if (c == ')')
numClose++;
}
if (numClose == 0)
return 0;
if (numClose == a.Length)
return a.Length;
int numOpen = 0;
for (int i=0; i < a.Length; i++)
{
var c = a[i];
if (c == '(')
numOpen++;
if (numOpen == numClose)
return (c == '(')? i+1 : i;
if (c == ')')
numClose--;
}
return 0;
}
static int split(String s) {
int i = -1;
int j = s.length();
int count = 0;
while(i+1<j) {
if(s.charAt(i+1)=='(' && s.charAt(j-1)==')') {
i++;
j--;
count++;
continue;
}
if(s.charAt(i+1)==')') {
i++;
}
if(s.charAt(j-1)=='(') {
j--;
}
}
if(count>0)
return j;
else
return s.length()-count;
}
static int split(String s) {
int i = -1;
int j = s.length();
int count = 0;
while(i+1<j) {
if(s.charAt(i+1)=='(' && s.charAt(j-1)==')') {
i++;
j--;
count++;
continue;
}
if(s.charAt(i+1)==')') {
i++;
}
if(s.charAt(j-1)=='(') {
j--;
}
}
if(count>0)
return j;
else
return s.length()-count;
}
def get_balancing_index(string):
left_counts, right_counts = [0, 0], [0, 0]
for c in string:
if c == '(':
left_counts[0] += 1
elif c == ')':
left_counts[1] += 1
for i in range(len(string)-1, -1, -1):
if left_counts[0] == right_counts[1]:
return i + 1
if string[i] == '(':
left_counts[0] -= 1
right_counts[0] += 1
elif string[i] == ')':
left_counts[1] -= 1
right_counts[1] += 1
return None
print(get_balancing_index('(())'))
print(get_balancing_index('(())))('))
print(get_balancing_index('))'))
k will always exist, 0<=k<=n
- Aditya March 24, 2017let's assume k was found at some position (denoted by |)
........|.....
now if a ) is added at the end, k remains the same since no. of )s on right half remain the same.
........|.....(
if a ) is added the end, then we have 1 extra ) on the right half, let's find the new k
if the immediate next bracket after the division (k+1 th bracket) was (, then sliding division partition by 1 position to the right balances the brackets again since no. of (s in left half also increases by 1 now.
........|(....) -> ........(|....)
if the immediate next bracket after the division (k+1 th bracket) was ), then sliding division partition by 1 position to the right balances the brackets again since no. of )s in right half also decreases by 1 now.
........|)....) -> ........)|....)
So, effectively if we have a given string and a k, appending a ) to the same string increases k by 1, appending ( to the same string doesn't change k.
Starting with an empty string, k = 0, start parsing the given string, for each ) ecnountered increase k by 1.
ans = no. of )s in the string