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

- Aditya March 24, 2017 | Flag Reply
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;
            }
        }

- maksymas March 21, 2017 | Flag Reply
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

- sandeep reddy March 21, 2017 | Flag Reply
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

- Gsreddi1994 March 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how does it work thou?

- maksymas March 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- maksymas March 21, 2017 | Flag Reply
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;
            }
        }

- Fa1987 March 22, 2017 | Flag Reply
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;
}
}

- sree March 22, 2017 | Flag Reply
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

- venky March 23, 2017 | Flag Reply
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

- adi.dtu March 24, 2017 | Flag Reply
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;

- zy March 28, 2017 | Flag Reply
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;

- zy March 28, 2017 | Flag Reply
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;

- Anonymous March 28, 2017 | Flag Reply
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[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).

- sonesh April 10, 2017 | Flag Reply
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;
}

- hnatsu April 27, 2017 | Flag Reply
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;
}

- hrshchaitanya April 27, 2017 | Flag Reply
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;
}

- hrshchaitanya April 27, 2017 | Flag Reply
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;

}

- hrshchaitanya April 27, 2017 | Flag Reply
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[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('))'))

- lalat.nayak July 05, 2017 | Flag Reply
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;

}

- Anon March 21, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More