Facebook Interview Question
InternsCountry: United States
Interview Type: Phone Interview
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, [])
#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))
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.
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.
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.
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
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.
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>>();
}
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.
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, ), ), ), ), )))
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;
}
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))"));
}
}
#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)))
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(")");
}
}
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;
}
I see a lot of
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:
- DevonMeyer212 September 05, 2013