Twitter电面

发一波面筋攒RP！考的是在一个有括号的string里找longest well formed subsequence, 比如“((()(

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

5):
啊啊啊～发完面筋就来二面了～烙印好nice啊～感动

norafang 发表于 2016-3-24 09:14
比如说(())和()()这两种情况的话，后一种用这个方法输出的就是()()，那前一种第二次pop“（”的时候你怎 ...

def longestSubsequence(s):
     #use stack and a int to record maxlength
     #if the stack append again, we need to recalculate the maxlength
    maxlength = 0
    length = 0
    stack = []
    rs = ""
    maxrs = ""
    for c in s:
        if not stack:
            if c ==")":
                length = 0
                rs = ""
            else:
                stack.append(c)
                rs +="("
        else:
            if c == "(":
                stack.append(c)
                rs +="("
            else:
                if stack.pop() == "(":
                    length +=2
                    rs +=")"
                # else:
                #     length = 0
        if len(maxrs)<len(rs):
            maxrs = rs
        if maxlength<length:
            maxlength = length
    return maxlength,maxrs

print longestSubsequence("())()()")

sorry我题目看错了。。其实道理一样。你可以用一个string来记录当前走过的parenthesis。然后判断stirng的长度，保留长度最长那个。这样其实就不用maxlength了。。我一直以为是要求最大长度。

sealove999 发表于 2016-3-27 01:55
楼主是这个代码的意思么

刚才那个是错的，看这个

1. public class Solution {
   
2.   public String findLongestWellFormatedSubstring(String s) {
   
3.     String ret = "";
   
4.     Deque<Integer> stack = new ArrayDeque<>();
   
5.     for (int i = 0; i < s.length(); i++) {
   
6.       if (s.charAt(i) == ')' && (!stack.isEmpty() && s.charAt(stack.peek()) == '(')) {
   
7.         stack.pop();
   
8.         int idx = stack.isEmpty() ? -1 : stack.peek();
   
9.         if (i - idx > ret.length()) {
   
10.           ret = s.substring(idx + 1, i + 1);
    
11.         }
    
12.       } else {
    
13.         stack.push(i);
    
14.       }
    
15.     }
    
16.     return ret;
    
17.   }
    
18. 
    
19.   public int findLongestWellFormatedSubstringLength(String s) {
    
20.     int ret = 0;
    
21.     Deque<Integer> stack = new ArrayDeque<>();
    
22.     for (int i = 0; i < s.length(); i++) {
    
23.       if (s.charAt(i) == '(') {
    
24.         stack.push(i);
    
25.       } else if (s.charAt(i) == ')') {
    
26.         if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
    
27.           stack.pop();
    
28.           ret = Math.max(ret, i - (stack.isEmpty() ? -1 : stack.peek()));
    
29.         } else {
    
30.           stack.push(i);
    
31.         }
    
32.       }
    
33.     }
    
34.     return ret;
    
35.   }
    
36. 
    
37.   public static void main(String[] args) {
    
38.     Solution ss = new Solution();
    
39.     String s = ")(()())";
    
40.     System.out.println(ss.findLongestWellFormatedSubstringLength(s));
    
41.     System.out.println(ss.findLongestWellFormatedSubstring(s));
    
42.   }
    
43. }
    

复制代码

楼主是这个代码的意思么

1. public class Solution {
   
2.   public String findLongestWellFormatedSubstring(String s) {
   
3.     String ret = "";
   
4.     Deque<Integer> stack = new ArrayDeque<>();
   
5.     for (int i = 0; i < s.length(); i++) {
   
6.       if (s.charAt(i) == '(') {
   
7.         stack.push(i);
   
8.       } else if (s.charAt(i) == ')') {
   
9.         if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
   
10.           stack.pop();
    
11.           int idx = stack.isEmpty() ? -1 : stack.peek();
    
12.           if (i - idx > ret.length()) {
    
13.             ret = s.substring(idx + 1, i + 1);
    
14.           }
    
15.         }
    
16.       }
    
17.     }
    
18.     return ret;
    
19.   }
    
20. 
    
21.   public int findLongestWellFormatedSubstringLength(String s) {
    
22.     int ret = 0;
    
23.     Deque<Integer> stack = new ArrayDeque<>();
    
24.     for (int i = 0; i < s.length(); i++) {
    
25.       if (s.charAt(i) == '(') {
    
26.         stack.push(i);
    
27.       } else if (s.charAt(i) == ')') {
    
28.         if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
    
29.           stack.pop();
    
30.           ret = Math.max(ret, i - (stack.isEmpty() ? -1 : stack.peek()));
    
31.         }
    
32.       }
    
33.     }
    
34.     return ret;
    
35.   }
    
36. 
    
37.   public static void main(String[] args) {
    
38.     Solution ss = new Solution();
    
39.     String s = "((()())";
    
40.     System.out.println(ss.findLongestWellFormatedSubstringLength(s));
    
41.     System.out.println(ss.findLongestWellFormatedSubstring(s));
    
42.   }
    
43. }
    

复制代码

lz电面之前收到5分钟的pre-interview question了吗？

gimook 发表于 2016-3-23 05:18
lz电面之前收到5分钟的pre-interview question了吗？

收到啦～～～～～～～～～～～～

lz没有oa 直接电面？

gimook 发表于 2016-3-23 05:18
lz电面之前收到5分钟的pre-interview question了吗？

前天晚上做的oa，刚才收到pre-interview question了

ahwhdsl 发表于 2016-3-23 05:48
前天晚上做的oa，刚才收到pre-interview question了

楼主怎么拿到机会的？内推？thanks！

同收到pre-interview question

求Are there any projects that you're interested in working on at Twitter?这一栏选projects的建议

lz是怎么选Are there any projects that you're interested in working on at Twitter?这里面的project的啊

楼主，能否问一下这道题是要return "(()())" 还是要return 6啊?

补充内容 (2016-3-23 06:20):
Never mind，i see.本质都是一样的嗯。。谢谢了啊