Posted tagged ‘interview’

K distance nodes in a Binary tree

February 3, 2012

For a Given node of a binary tree, print the K distance nodes.

For the solution, you can also refer to stackoverflow. This also tells that only one ancestor can be at K distance from a given node.

Source code: (written in C)

void K_dist_children(node * nd, int K)
{
// Base case
// The Kth child found
if(K==0)
{
printf("%d\n", nd->val);
return;
}

// K distance node from nd are at
// K-1 distance from children of current node
K_dist_children(nd->left, K-1);
K_dist_children(nd->right, K-1);
}

int K_dist_ancestor(node * cur,    //curent node
node * search, //node being searched
int K)
{
// If the node is found, return back the result
if (cur == search)
{
return K-1;
}

int n1, n2;

// recursively search for the node in the tree
n1 = K_dist_ancestor(cur->left, search, K);
n2 = K_dist_ancestor(cur->right, search, K);

// PS: n1 & n2 can't be non-(-1) at the same time

// if node found in any of the sub trees
if((n1 == -1) && (n2 == -1))
return -1;

// node found in right subtree
if((n1 == -1))
{
// the current node is at distance K
if(n2 == 0)
printf("%d", cur->val);

// return back the distance
return (n2-1);
}

// node found in left subtree
if((n2 == -1))
{
// the current node is at distance K
if(n1 == 0)
printf("%d", cur->val);

// return back the distance
return (n1-1);
}
}

void print_K_distance_nodes(node * root, node * search, int K)
{
// The structure of node is:
// struct node{
// int val;
// node * left;
// node * right;
// }

// Print the ancestor at distance K
K_dist_ancestor(root, search, K);

// Print the children at distance K
K_dist_children(search, K);
}

Python script to get all the distinct substrings from a string

August 11, 2011

Recently I came across an interview question:

Print out all the substrings of a given string.?

Now, the catch in the question is for strings like “ababc”. If you are blindly adding the substrings to a storage you have, you will end up with copies of “ab”, which is not what we want. Now, what is the best method to avoid duplicates..??
Ans: hash tables.. 😉

Thus, using the power of Python (i.e. the sets available in python) I have written the following script which takes the string as an input and returns the set of the substrings.

def substr(string):
    j=1
    a=set()
    while True:
        for i in range(len(string)-j+1):
            a.add(string[i:i+j])
        if j==len(string):
            break
        j+=1
        #string=string[1:]
    return a

Also, to print the set sequentially, we can easily convert the returned set to an ordered list. For example, here I have sorted the list based on the length of the substrings.

def prnt(seta):
    l=list(seta)
    l.sort(key=lambda(x):len(x))
    print l
    ## return l # if you want to return this object too

The normal execution on the commandline looks like this:

>>> x
 set(['a', 'ayus', 'h', 'yus', 'ayush', 'us', 'ush', 'ay', 's', 'sh', 'u', 'yush', 'y', 'yu', 'ayu'])
>>> prnt(x)
 ['a', 'h', 's', 'u', 'y', 'us', 'ay', 'sh', 'yu', 'yus', 'ush', 'ayu', 'ayus', 'yush', 'ayush']

Complexities:
time O(n**2) ## worst but this method provides us with the substrings also
memory O(2**n) ## worst when all characters in the string are different

Some good python interview questions

June 17, 2011

Some questions I had from somewhere. Since I feel somewhat capable of myself, I try to answer them here..

Edit: After all I got that “somewhere” 🙂 The writer is a fellow python enthusiast and has given me the permission to use his questions on my blog (though the answers are to be mine.. :). Thank you Ronak..

Edit: Thanks a lot David Lawrence (Endophage) for your eminent input to modify this post.

1. Name five modules that are included in python by default (many people come searching for this, so I included some more examples of modules which are often used)

datetime           (used to manipulate date and time)
re                         (regular expressions)
urllib, urllib2  (handles many HTTP things)
string                  (a collection of different groups of strings for example all lower_case letters etc)
itertools            (permutations, combinations and other useful iterables)
ctypes                (from python docs: create and manipulate C data types in Python)
email                  (from python docs: A package for parsing, handling, and generating email messages)
__future__      (Record of incompatible language changes. like division operator is different and much better when imported from __future__)
sqlite3               (handles database of SQLite type)
unittest             (from python docs: Python unit testing framework, based on Erich Gamma’s JUnit and Kent Beck’s Smalltalk testing framework)
xml                     (xml support)
logging              (defines logger classes. enables python to log details on severity level basis)
os                        (operating system support)
pickle                (similar to json. can put any data structure to external files)
subprocess    (from docs: This module allows you to spawn processes, connect to their input/output/error pipes, and obtain their return codes)
webbrowser  (from docs: Interfaces for launching and remotely controlling Web browsers.)
traceback       (Extract, format and print Python stack traces)

2. Name a module that is not included in python by default

mechanize
django
gtk

A lot of other can be found at pypi.

3. What is __init__.py used for?

It declares that the given directory is a module package. #Python Docs (From Endophage‘s comment)

4. When is pass used for?

pass does nothing. It is used for completing the code where we need something. For eg:

class abc():
    pass

5. What is a docstring?

docstring is the documentation string for a function. It can be accessed by

function_name.__doc__

it is declared as:

def function_name():
"""your docstring"""

Writing documentation for your progams is a good habit and makes the code more understandable and reusable.

6. What is list comprehension?

Creating a list by doing some operation over data that can be accessed using an iterator. For eg:

>>>[ord(i) for i in string.ascii_uppercase]
     [65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90]
 >>>

7. What is map?

map executes the function given as the first argument on all the elements of the iterable given as the second argument. If the function given takes in more than 1 arguments, then many iterables are given.  #Follow the link to know more similar functions
For eg:

>>>a='ayush'
>>>map(ord,a)
....  [97, 121, 117, 115, 104]
>>> print map(lambda x, y: x*y**2, [1, 2, 3], [2, 4, 1])
....  [4, 32, 3]

 

 Help on built-in function map in module __builtin__:

map(...)
map(function, sequence[, sequence, ...]) -> list

Return a list of the results of applying the function to the items of
the argument sequence(s).  If more than one sequence is given, the
function is called with an argument list consisting of the corresponding
item of each sequence, substituting None for missing values when not all
sequences have the same length.  If the function is None, return a list of
the items of the sequence (or a list of tuples if more than one sequence).

#Python Docs

8. What is the difference between a tuple and a list?

A tuple is immutable i.e. can not be changed. It can be operated on only. But a list is mutable. Changes can be done internally to it.

tuple initialization: a = (2,4,5)
list initialization: a = [2,4,5]

The methods/functions provided with each types are also different. Check them out yourself.

9. Using various python modules convert the list a to generate the output ‘one, two, three’

a = ['one', 'two', 'three']
Ans:   ", ".join(a)

 

>>>help(str.join)
Help on method_descriptor:
 join(...)
 S.join(iterable) -> string
 Return a string which is the concatenation of the strings in the
 iterable.  The separator between elements is S.

10. What would the following code yield?

word = 'abcdefghij'
print word[:3] + word[3:]

Ans: ‘abcdefghij’ will be printed.
This is called string slicing. Since here the indices of the two slices are colliding, the string slices are ‘abc’ and ‘defghij’. The ‘+’ operator on strings concatenates them. Thus, the two slices formed are concatenated to give the answer ‘abcdefghij’.

11. Optimize these statements as a python programmer.

word = 'word'
print word.__len__()

Ans:

word = 'word'
print len(word)

12. Write a program to print all the contents of a file

Ans.

try:
    with open('filename','r') as f:
        print f.read()
except IOError:
    print "no such file exists"

13. What will be the output of the following code

a = 1
a, b = a+1, a+1
print a
print b

Ans.
2
2

The second line is a simultaneous declaration i.e. value of new a is not used when doing b=a+1.

This is why, exchanging numbers is as easy as:

a,b = b,a

😀

14. Given the list below remove the repetition of an element.
All the elements should be unique
words = [‘one’, ‘one’, ‘two’, ‘three’, ‘three’, ‘two’]

Ans:
A bad solution would be to iterate over the list and checking for copies somehow and then remove them!

One of the best solutions I can think of right now:

a = [1,2,2,3]
list(set(a))

set is another type available in python, where copies are not allowed. It also has some good functions available used in set operations ( like union, difference ).

15. Iterate over a list of words and use a dictionary to keep track of the frequency(count) of each word. for example

{‘one’:2, ‘two’:2, ‘three’:2}

Ans:

>>> def dic(words):
  a = {}
  for i in words:
    try:
      a[i] += 1
    except KeyError: ## the famous pythonic way:
      a[i] = 1       ## Halt and catch fire
  return a

>>> a='1,3,2,4,5,3,2,1,4,3,2'.split(',')
>>> a
['1', '3', '2', '4', '5', '3', '2', '1', '4', '3', '2']
>>> dic(a)
{'1': 2, '3': 3, '2': 3, '5': 1, '4': 2}

Without using try-catch block:

>>> def dic(words):
  data = {}
  for i in words:
    data[i] = data.get(i, 0) + 1
  return data

>>> a
['1', '3', '2', '4', '5', '3', '2', '1', '4', '3', '2']
>>> dic(a)
{'1': 2, '3': 3, '2': 3, '5': 1, '4': 2}

PS: Since the collections module (which gives you the defaultdict) is written in python, I would not recommend using it. The normal dict implementation is in C, it should be much faster. You can use timeit module to check for comparing the two.
So, David and I have saved you the work to check it. Check the files on github. Change the data file to test different data.

16. Write the following logic in Python:
If a list of words is empty, then let the user know it’s empty, otherwise let the user know it’s not empty.

Ans.

Can be checked by a single statement (pythonic beauty):

print "The list is empty" if len(a)==0 else "The list is not empty"

>>> a=''
>>> print "'The list is empty'" if len(a)==0 else "'The list is not empty'"
'The list is empty'
>>> a='asd'
>>> print "'The list is empty'" if len(a)==0 else "'The list is not empty'"
'The list is not empty'

17. Demonstrate the use of exception handling in python.

Ans.

try:
  import mechanize as me
except ImportError:
  import urllib as me

## here you have atleast 1 module imported as me.
This is used to check if the users computer has third party libraries that we need. If not, we work with a default library of python. Quite useful in updating softwares.
PS: This is just one of the uses of try-except blocks. You can note a good use of these in API’s.
Also note that if we do not define the error to be matched, the except block would catch any error raised in try block.

18. Print the length of each line in the file ‘file.txt’ not including any whitespaces at the end of the lines.

with open("filename.txt", "r") as f1:
  for line in f1:
    print len(line.rstrip())

rstrip() is an inbuilt function which strips the string from the right end of spaces or tabs (whitespace characters).

19. Print the sum of digits of numbers starting from 1 to 100 (inclusive of both)

Ans.

print sum(range(1,101))

range() returns a list to the sum function containing all the numbers from 1 to 100. Please see that the range function does not include the end given (101 here).

print sum(xrange(1, 101))

xrange() returns an iterator rather than a list which is less heavy on the memory.

20. Create a new list that converts the following list of number strings to a list of numbers.

num_strings = [‘1′,’21’,’53’,’84’,’50’,’66’,’7′,’38’,’9′]

Ans.
use a list comprehension

 >>> [int(i) for i in num_strings]
[1, 21, 53, 84, 50, 66, 7, 38, 9]

#num_strings should not contain any non-integer character else ValueError would be raised. A try-catch block can be used to notify the user of this.

Another one suggested by David using maps:

>>> map(int, num_strings)
    [1, 21, 53, 84, 50, 66, 7, 38, 9]

21. Create two new lists one with odd numbers and other with even numbers
num_strings = [1,21,53,84,50,66,7,38,9]

Ans:

>>> odd=[]
>>> even=[]
>>> for i in n:
    even.append(i) if i%2==0 else odd.append(i)

## all odd numbers in list odd
## all even numbers in list even

Though if only one of the lists were requires, using list comprehension we could make:

even = [i for i in num_strings if i%2==0]
odd = [i for i in num_strings if i%2==1]

But using this approach if both lists are required would not be efficient since this would iterate the list two times.!

22. Write a program to sort the following intergers in list

nums = [1,5,2,10,3,45,23,1,4,7,9]

nums.sort() # The lists have an inbuilt function, sort()
sorted(nums) # sorted() is one of the inbuilt functions)

Python uses TimSort for applying this function. Check the link to know more.

23. Write a for loop that prints all elements of a list and their position in the list.
Printing using String formatting

(Thanks endophage for correcting this)

>>> for index, data in enumerate(asd):
....    print "{0} -> {1}".format(index, data)

0 -> 4
1 -> 7
2 -> 3
3 -> 2
4 -> 5
5 -> 9

#OR

>>> asd = [4,7,3,2,5,9]

>>> for i in range(len(asd)):
....    print i+1,'-->',asd[i]

1 --> 4
2 --> 7
3 --> 3
4 --> 2
5 --> 5
6 --> 9

24. The following code is supposed to remove numbers less than 5 from list n, but there is a bug. Fix the bug.

n = [1,2,5,10,3,100,9,24]

for e in n:
  if e<5:
    n.remove(e)
  print n

## after e is removed, the index position gets disturbed. Instead it should be:

a=[]
for e in n:
  if e >= 5:
    a.append(e)
n = a

OR again a list comprehension: 😉

return [i for i in n if i >= 5]

OR use filter

return filter(lambda x: x >= 5, n)

25. What will be the output of the following

def func(x,*y,**z):
....    print z

func(1,2,3)

Ans.

Here the output is :

{}  #Empty Dictionay

x is a normal value, so it takes 1..
y is a list of numbers, so it takes 2,3..
z wants named parameters, so it can not take any value here.
Thus the given answer.

26. Write a program to swap two numbers.

a = 5
b = 9

as i told earlier too, just use:
a,b = b,a

27. What will be the output of the following code

class C(object):
....    def__init__(self):
....        self.x =1

c=C()
print c.x
print c.x
print c.x
print c.x

Ans.

All the outputs will be 1, since the value of the the object’s attribute(x) is never changed.

1
1
1
1

x is now a part of the public members of the class C.
Thus it can be accessed directly..

28. What is wrong with the code

func([1,2,3]) # explicitly passing in a list
func()        # using a default empty list

def func(n = []):
#do something with n

print n

Ans. This would result in a NameError. The variable n is local to function func and can’t be accessesd outside. So, printing it won’t be possible.

Edit: An extra point for interviews given by Shane Green and Peter: “””Another thing is that mutable types should never be used as default parameter values. Default parameter value expressions are only evaluated once, meaning every invocation of that method shares the same default value. If one invocation that ends up using the default value modifies that value–a list, in this case–it will forever be modified for all future invocations. So default parameter values should limited to primitives, strings, and tuples; no lists, dictionaries, or complex object instances.”””
Reference: Default argument values

29. What all options will work?

a.
n = 1
print n++   ## no such operator in python (++)

b.
n = 1
print ++n   ## no such operator in python (++)

c.
n = 1
print n += 1  ## will work

d.
int n = 1
print n = n+1 ##will not work as assignment can not be done in print command like this

e.
n =1
n = n+1      ## will work

30. In Python function parameters are passed by value or by reference?

Ans. By value (check if you want to, I also did the same 😉 It is somewhat more complicated than I have written here (Thanks David for pointing). Explaining all here won’t be possible. Some good links that would really make you understand how things are:

Stackoverflow

Python memory management

Viewing the memory

31.Remove the whitespaces from the string.

s = ‘aaa bbb ccc ddd eee’

Ans.

''.join(s.split())
## join without spaces the string after splitting it

OR

filter(lambda x: x != ‘ ‘, s)

32. What does the below mean?

s = a + ‘[‘ + b + ‘:’ + c + ‘]’

seems like a string is being concatenated. Nothing much can be said without knowing types of variables a, b, c. Also, if all of the a, b, c are not of type string, TypeError would be raised. This is because of the string constants (‘[‘ , ‘]’) used in the statement.

33. Optimize the below code

def append_s(words):
  new_words=[]
  for word in words:
    new_words.append(word + 's')
  return new_words

for word in append_s(['a','b','c']):
  print word

The above code adds a trailing s after each element of the list.

def append_s(words):
return [i+’s’ for i in words] ## another list comprehension 😀

for word in append_s([‘a’,’b’,’c’]):
print word

34. If given the first and last names of bunch of employees how would you store it and what datatype?

Ans. best stored in a list of dictionaries..
dictionary format:  {‘first_name’:’Ayush’,’last_name’:’Goel’}

Since most of the code here gets messed up, I have created a repo on github named Python(blog) which lists all the required code.

Up-vote/share the post if you liked it. Thanks!


%d bloggers like this: