## Amazon Interview Question for SDE-2s

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

it is just one line answer

if you calculate the closed brackets thats the answer.

for example 1 )) ans: 2
example 2 (( ans : 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the place where Lateral thinking is usefull.

no. of closed brackets = answer

for example : )) == 2
(( == 0;
(())==2;
)))==3;

thats so simple

Comment hidden because of low score. Click to expand.
0
of 0 vote

how does it work thou?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How does it work for ))))))))(

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

k = total number of closed brackets

for ex: if there is only one open bracket in first k elements, there has to be only 1 closed bracket from k+1 to n as there are only k closed brackets. similarly 2,3 etc

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

int start = 0;
int end = input.Length - 1;
while (start < end)
{
if (input[start] != '(')
{
start++;
}
else
{
if (input[end] == ')')
{
start++;
}

end--;
}
}

return end;

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int start = 0;
int end = input.Length - 1;
while (start < end)
{
if (input[start] != '(')
{
start++;
}
else
{
if (input[end] == ')')
{
start++;
}

end--;
}
}

return end;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int start = 0;
int end = input.Length - 1;
while (start < end)
{
if (input[start] != '(')
{
start++;
}
else
{
if (input[end] == ')')
{
start++;
}

end--;
}
}

return end;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 == '(')
{
openBracketsArray = 1;
closeBracketsArray = 0;
}
else
{
openBracketsArray = 0;
closeBracketsArray = 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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def get_balancing_index(string):
left_counts, right_counts = [0, 0], [0, 0]
for c in string:
if c == '(':
left_counts += 1
elif c == ')':
left_counts += 1
for i in range(len(string)-1, -1, -1):
if left_counts == right_counts:
return i + 1
if string[i] == '(':
left_counts -= 1
right_counts += 1
elif string[i] == ')':
left_counts -= 1
right_counts += 1
return None

print(get_balancing_index('(())'))
print(get_balancing_index('(())))('))
print(get_balancing_index('))'))``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static int matchBrace(String str){
int i = 0;
int j = str.length()-1;
while(i < j){
if(str.charAt(i) == ')'){
i++;

}
if(str.charAt(j) == '('){
j--;
}
if(str.charAt(i) == '(' && str.charAt(j) == ')'){
i++;
j--;
}
}
return i+1;``````

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.