Facebook Interview Question for Interns


Country: United States
Interview Type: Phone Interview




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

I see a lot of

if isinstance(i, int):
		print i

but as referenced here:
stackoverflow-dot-com/questions/3501382/checking-whether-a-variable-is-an-integer-or-not

it is better to assume your item is a list, and if it is not, run certain code on what you know, now, to be an integer. As can be seen here:

def lists_in_lists(item):
	try:
		for i in item:
			lists_in_lists(i)
	except TypeError:
		print item

lists_in_lists([[[[[[[5]]]]]]])
#$> 5
lists_in_lists([[0, [1, 2, 3, 4], 5, [6, 7, [8, 9], 10]]])
#$> 0 1 2 3 4 5 6 7 8 9 10 separated by \n

- DevonMeyer212 September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
7
of 7 vote

def parse_list(tlist, out):
  for el in tlist:
    if isinstance(el, int):
      out.append(el)
    else: 
      out = parse_list(el, out)
  return out

print parse_list(tlist, [])

- Baldwin Hafstein November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This should work. Consider this to be a DFS traversal.

- SR December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

#use recursive to flat all the way to element, and then append back to single tuple element, similar for list implementation too.

a_tuple = (1, (2, 3), (4, (5, 6), 7))
def flat(a):
	if isinstance(a,int):
		return (a,)
	else:		
		fulltuple=();	
		for i in range(len(a)):
			fulltuple+=flat(a[i])
		return fulltuple
print (flat(a_tuple))

- mailming December 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, I think this is what they were looking for. Thanks!

- panoptic.biopower December 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import re
#LOL, this is the Power of Python
a_input=(1, (2, 3), (4, (5, 6), 7))
num=re.compile('\d')
print (tuple(map(int,num.findall(str(a_input)))))

- mailming December 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Should the output for both ((((5)))) and ( 5 ) be ( 5 )?

- Anonymous November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, it should Sorry I didn't make that clear.

- Anonymous November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the varying grouping of list in the input does not affect the output single list, then this should be fairly easy.
(1, (2, 3), (4, (5, 6), 7)) output (1, 2, 3, 4, 5, 6, 7)
(1, (2, 3), (4, 5), (6, 7)) output (1, 2, 3, 4, 5, 6, 7)
......

1. Keep the leftest "(" and rightest ")"
2. Remove any "(" and ")" between
3. Detect delimiter "," and found the number.

Code wise is easy. Sometimes this kind of interview is quick tricky. Throw you piles of information. Sometimes need to peel off the distraction and simplify the problem.

- peter tang November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I started with some really complex node structure and thinking of using tree structure (with pointer to the next and sibling). And think of using recursive implementation to find out a algorithm.

Later it turns out if the output is always the sequence of the order of each number appearing in the list, then the data structure is not really matter.

So come up this solution. The only thing that bothering me is that do some sanity checking of the string. Basically check the brackets appearing in pair. But this is not very difficult.

- peter tang November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry I was unclear in the initial prompt - you do not get a string as an input.
You get a data structure that contains a number and/or a list, as specified above. At least this was my interpretation from what the interviewer told me on the phone, but perhaps I mis-understood.

- Anonymous November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

why don't you simply scan the string from the second element to the second to last element, and just ignore anything in it besides numbers and commas. you can have a running string that has the elements so far. then you slap a left and right parenthesis at the end and voila. however, the solution seems too simple. maybe i'm missing something.

- bk November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

As I said above, you do not get a string as an input

- panoptic.biopower November 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

use a stack.
1. push all the elements in the original list into a stack in reversed order
2. get the top element in the stack,
2.a if the element is a list: push all the elements in this list into the stack in reversed order
2.b if the element is a number: append to the result list.

def flat_list(alist):
	assert alist
	stack = alist[::-1]
	result = []
	while stack:
		first = stack.pop()
		if isinstance(first, list):
			for e in first[::-1]:
				stack.append(e)
		else:
			result.append(first)
	return result

- gnahzy November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have received similar question during one of my interviews: Create an Iterator over collection which may contains single objects or nested collections.

Like this:

List<Object> data = new ArrayList<Object>();
data.add( 1 );
data.add( Arrays.asList(2,3) );

So it's not just a string where you can remove all '(' and ')' character and just iterate over.

- m@}{ November 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NestedListsIterator<T> implements Iterator<T> {

	
	public NestedListsIterator(List<Object> list) {
		super();
		
		if( list == null ){
			throw new IllegalArgumentException("'list' parameter is NULL");
		}
		
		this.curIt = list.iterator();	
		this.element = getNextElement();
	}

	@Override
	public boolean hasNext() {
		return element != null;
	}

	@Override
	public T next() {
		
		if( ! hasNext() ){
			throw new NoSuchElementException();
		}
		
		T retValue = element;		
		element = getNextElement();
		
		return retValue;
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException();		
	}
	
	
	/**
	 * 
	 * @return next available element or NULL if not exists
	 */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	private T getNextElement(){
		
		Object obj = null;
		
		while( true ){	
			
			if( ! curIt.hasNext() && delayedData.isEmpty() ){
				return null;
			}
			
			if( curIt.hasNext() ){	
				
				obj = curIt.next();
				
				// list (maybe nested list)	
				if( obj instanceof List ){								
					delayedData.push( curIt );
					curIt = ((List) obj).iterator();
				}
				// single element
				else {
					return (T)obj;
				}							
			}
			else {		
				curIt = delayedData.pop();
			}
		}
		
	}
	
	
	private T element;
	private Iterator<Object> curIt;	
	private final Deque<Iterator<Object>> delayedData = new ArrayDeque<Iterator<Object>>();


}

- m@}{ November 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def f(L):
res = []
for i in L:
if IsList(L): res += f(i)
else: res += [i]
return res

- Ghost November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def flatten(input):
        if isinstance(input, int):
                yield input
        else:
                for elem in input:
                        for nested in flatten(elem):
                                yield nested

- Chad Parry November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Hey, why not just remove all "{" and "}", that's it?

if it encountered "{" or "}“, just remove it.

quite not sure what this question is about. defenitely u can write recurrsive function to remove it.

- albert November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also note that if the input is not a string but a tree kind of structure(may be a n-ary tree), then inorder traversal would suffice.

- ALgeek November 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python generator is easy to use

def flat_list(l):
    assert isinstance(l, list) or isinstance(l, tuple)
    for i in l:
        if isinstance(i, list):
            for j in flat_list(i):
                yield j
        elif isinstance(i, tuple):
            for j in flat_list(list(i)):
                yield j
        else:
            yield i


print tuple(flat_list((1, (2, 3, ), (4, (5, 6, ), 7, ), ((((8, ), ), ), ), )))

- Anonymous November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

scheme code

(define strip
(lambda(lst)
(cond
((null? lst) lst)
((atom? (car lst)) (cons (car lst) (strip (cdr lst))))
(else (append (strip (car lst)) (strip (cdr lst)))))))

> (strip '(1 (2 3) (4 (5 6) 7)))
(1 2 3 4 5 6 7)
> (strip '((((5)))))
(5)

- Anonymous November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

C++ implementation:

void outputNakedString(char* str){
        
    string myString = "(";
    
    for(int i=0; i<strlen(str); i++)
    {
        if(str[i]!='(' && str[i]!=')')
        {
            myString+= str[i];
        }
    }
    myString+=")";
    cout<<myString;
}

- M November 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

should check for ',' as well

- tranquil November 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RemoveBrackets {
public String removeBrackets(String str) {
StringBuffer sb = new StringBuffer();
sb.append('(');
int count = 1;
for (int i = 0; i < str.length(); i++) {
char currentvalue = str.charAt(i);
if (currentvalue != '(' && currentvalue != ')'
&& currentvalue != ',' && currentvalue != ' ') {
System.out.println("currentvalue is" + currentvalue);
// System.out.println("count is"+count);
// System.out.println("actual value is "+String.valueOf(str.charAt(i)));
if (count > 1)
sb.append(",");
sb.append(str.charAt(i));

count++;
}
}
sb.append(')');

return sb.toString();
}

public static void main(String args[]) {
RemoveBrackets rmBrackets = new RemoveBrackets();
System.out.println(rmBrackets.removeBrackets("((((5))))"));
System.out.println(rmBrackets
.removeBrackets("(1,(2, 3), (4, (5, 6), 7))"));
}

}

- luckysing November 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#cannot find any clean way to use split
import re
a_input=(1, (2, 3), (4, (5, 6), 7))
sep=re.compile('[(,) ]+')
b_string=sep.split(str(a_input))
#always got empty string after splitting, anyone can brighten this up?
while '' in b_string: b_string.remove('')
print (tuple(map(int,b_string)))

- mailming December 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int char1;
while((char1 = getchar())!=EOF)
if (char1 == '(' || char1 == ')') continue;
else printf("%c", char1);
}

- Anonymous December 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the composite design pattern. It will work.

- Anonymous January 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/python

def flatten(l):
  res=list()
  t=type(res)
  for e in l:
    if type(e)==t:
      res.extend(flatten(e))
    else:
      res.append(e)
  return res

if __name__=='__main__':
  l=[1, [2, 3], [4, [5, 6], 7]]
  l=[[[[[5]]]]]
  print flatten(l)

- light January 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my java code is below to solve problem , however only one problem is, it puts comma at the and of the number as well :)))

public class Main
{


public static void main (String[] args)
{

String s1 = "((((((555";




char[] chars = s1.toCharArray();


System.out.print("(");

int lastcomaremover = (s1.length()-1);

for(int i=0 ; i<s1.length(); i++)
{


if ( ' ' == chars[i] || ',' == chars[i] || '('== chars[i] || ')' == chars[i])
{
continue;

}
else
{

System.out.print(chars[i]);
System.out.print(',');



}
}



System.out.println(")");


}

}

- mustafa February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looks to me like a trick question. Everyone who tries more than just skipping all non-digit characters won't get the job.

- FBNerd February 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static string Parse(string s)
        {
            int index = 0;
            return "(" + Parse(s, ref index).ToString() + ")";
        }

        private static StringBuilder Parse(string s, ref int index)
        {
            StringBuilder result = new StringBuilder();

            while (index < s.Length && s[index] != ')')
            {
                if (s[index] == '(')
                {
                    index++;
                    result.Append(Parse(s, ref index));
                }
                else result.Append(s[index]);

                index++;
            }

            return result;
        }

- ZuZu May 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def dfs(s):

	for i in s:
		if isinstance(i,int):
			print i,
		else:
		   dfs(i)

- Rohit June 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String Parse(String s){
    int len = s.length();
    StringBuffer buf = new StringBuffer();
    for(int i = 0 ; i < len ; i++){
      if(s.charAt(i) != '(' !! s.charAt(i)!=')'){
        buf.add(s.charAt(i));
      }
    }
    return buf.toString();
  }

- Anonymous October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def flatten(arr):
    if isinstance(arr, int):
        return [arr]

    # Otherwise we're a list
    flat_list = []
    for i in arr:
        flat_list += flatten(i)
    return flat_list

- twigfiggly October 27, 2013 | 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