Uber Interview Question for Senior Software Development Engineers


Country: India
Interview Type: Phone Interview




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

import java.util.*;

public class ValidParentheses {


    public static void main(String[] args) {

        final Map<Integer, List<String>> cache = new HashMap<>();
        long start= System.currentTimeMillis();
        List<String> result = new ValidParentheses().generate(11, cache);
        long end  = System.currentTimeMillis();

        for (String s : result) {
            System.out.println(s);
        }
        System.out.println(result.size());
        System.out.printf("Total ms elapsed " + (end- start));
    }


    public List<String> generate(int n, Map<Integer, List<String>> cache) {
        if (cache.containsKey(n)) {
            System.out.printf("expression for i=%d requested & found in cache%n", n);
            return cache.get(n);
        } else {
            System.out.printf("expression for i=%d requested & NOT found in cache%n", n);
        }
        if (n == 0) {
            List<String> list = new ArrayList<>(Arrays.asList(""));
            cache.put(n, list);
            return list;
        }

        if (n == 1) {
            List<String> list = new ArrayList<>(Arrays.asList("()"));
            cache.put(n, list);
            return list;
        }

        if (n == 2) {
            List<String> list = new ArrayList<>(Arrays.asList("()()", "(())"));
            cache.put(n, list);
            return list;
        }

        // for n=3 or above, let this method calculate and cache
        List<String> result = new ArrayList<>();

        for (int i = 0; i < n; ++i)
            for (String in : generate(i, cache))
                for (String out : generate(n - 1 - i, cache))
                    result.add("(" + in + ")" + out);

        cache.put(n, result);
        return result;
    }
}

- Makarand August 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
typedef long long int int64;
void paren(int64 n, int64 m , string s){
	if(m==0) {
		cout<<s<<endl;
		return ;
	}
	if(n>0) {
		s.append("{");
		paren( n -1 , m , s );
		s.pop_back();
	}
	if(n<m){
		s.append("}");
		paren( n , m - 1 , s );
		s.pop_back();
	}
}
int main(){
	int64 n;
	cin>>n;
	paren( n , n , "");
}

- shashanksi2009 September 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def fun(i,closed,ar,n):
    if i==2*n:
        print(ar)
        return
    op=i-closed;
    if(closed<n):
        fun(i+1,closed+1,ar+'(',n)
    if(op<closed):
        fun(i+1,closed,ar+')',n)

- raj April 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def fun(i,closed,ar,n):
    if i==2*n:
        print(ar)
        return
    op=i-closed;
    if(closed<n):
        fun(i+1,closed+1,ar+'(',n)
    if(op<closed):
        fun(i+1,closed,ar+')',n)

- raj April 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Parenthesis {

	static void pp(int lL, int rL, int pos, char[] str){
		if(lL < 0 || lL > rL)
			return;
		
		if((lL==rL && rL==0)){
			System.out.println(str);
			return;
		}
		
		if(pos >= str.length)
			return;
		
		str[pos] = '(';
		pp(lL-1, rL, pos+1, str);
		str[pos] = ')';
		pp(lL, rL-1, pos+1, str);
	}
	
	public static void main(String[] args) {
		int n = 9;
		int pairs = n/2;
		char[] str = new char[pairs*2];
		pp(pairs, pairs, 0, str);
	}

}

- lareinev May 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<String> getAllParanthesis(int left, int right) {
        List<String> result = new ArrayList<>();
        int pp = Math.min(left, right);
        helper(0, 0, pp, pp, new StringBuilder(), result);
        return result;
    }

    public static void helper(int lc, int rc, int lrem, int rrem, StringBuilder sb, List<String> list) {
        if (lrem == 0 && rrem == 0) {
            list.add(sb.toString());
            return;
        }
        if (lrem > 0) {
            sb.append('(');
            helper(lc + 1, rc, lrem - 1, rrem, sb, list);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (rrem > 0 && lc > rc) {
            sb.append(')');
            helper(lc, rc + 1, lrem, rrem - 1, sb, list);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

- kogkoge April 02, 2019 | 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