Placement Papers for All Companies

3i infotech
Abacus Infotech
Abatix
Abaxis
ABB
ACC Limited
Accel Frontline
Accenture
Aditi Technologies
Adobe System
ADP
Agilysys
AgreeYa
AIG
AirNet
Alanco Technologies
Alle Technologies
Allfon
Alter Systems
Amazon
AMDL
Amdocs
AMI
Amiti Software Technologies
ANZ
Apple
Applied Materials
Apps Associates
Aricent
ASDC
Ashok Leyland Ltd
Asian Paints
Aspire System
AT & T
Atlas Copco
Atos Origin
AXA Technology Services
Axes Technology
Bain
Bajaj
Bayer
Bharti Airtel Ltd
Bhawan Cybertek
Birlasoft
Blue Star Infotech
BMC
BOB
Brakes India
C-DOT
CA Technologies
Cadence
Calsoft
Canarys
Capgemini
Caterpillar
Celstream
CGI Group
Changepond Technologies
Cimtrix Systems
Cisco system
Citicorp Overseas Software Ltd
ClinTech
CMC Limited
CMS
Cognizant
Compaq
Consagous Technologies
Convergys
CORDYS
CRISIL
Crompton Greaves
CSC
CSFB
CtrlS Datacenters Ltd
Cummins
Cyient
Daffodil
Daimler
Dell
Deloitte
Delphi-TVS
Dharma Systems
Directi
DSRC
Eicher
ELGI
ELICO
EMC Corporation
Emphasis
Ericsson
Ernst & Young
ESKO
Essar
Facebook
Fanuc Corporation
Fidelity
Flextronics
Flipkart
Freescale
Fujitsu
Gajshield
GE
Genpact India
Geodesic
Geometric Limited
GlobalEdge
GlobalLogic
GMR Group
Godrej Infotech
Google
Grapecity
Harita - TVS
HCL
HCL Technologies
Headstrong
Healthasyst
HEC Ltd
Hexaware
HFCL
Holool
Honeywell
HP
HTC Global Services
Huawei
Hughes
Hyundai
IBM
IBS Software Services
IGate
Ikanos
IKOS
Impetus
iNautix
Indecomm
IndiaBulls Power Limited
Inductis-EXL
Industrial Alliance
Infineon
Infogain
Infosys
Intec
Integra
Intel
Intergraph
ITC Infotech
Jindal Steel and Power Limited
KPIT
L & T
L & T Infotech
LG Soft
Linde India Ltd
LnT Emsys
LnT-ECC
Lucas - TVS
Mahindra Engineering Services Ltd
Mahindra Ltd
Maruti
Matrix
Maveric Systems
McAfee
Microland
Microsoft
Mindtree
Miraclesoft
MKCL
Motorola
Mu-Sigma
Nagarro
NASSCOM
NCR Corporation
Ness Technologies
Neudesic
NIIT Technologies
Novell
Nvidia
Oracle
Persistent
Philips
Planetasia
Polaris
Poornam Info Vision
PSI Data Systems Limited
Quest-Global
Quinnox
R Systems
Redpine
Reliance Energy
Robert Bosch
RS Software
Samsung
SAP labs India
Sapient
Sasken Communications
Schneider India
Serco
Siemens
Sierra Atlantic
SkyTECH
Soliton
Sonata Software
Sony India
SQL Star
Steria
Subex Limited
Sutherland Global Services
Syntel
Talisma
Tata motors
Tata technologies
Tata-ELXSI
TCE
TCS
Tech Mahindra
Temenos
Tesco
Texas Instruments
Thermax
ThoughtWorks
Torry Harris
Triad
Trianz
Trilogy
TVS Motor
Unisys
UnitedHealth Group
UST Global
UTC Aerospace System
Valuelabs
Vedanta
Verifone
Verizon
Virtusa
Vision Infotech
Vizual
VMware
Wipro
Yahoo
YASH Technologies
Zenith
Zensar Technologies
ZTE

Facebook Interview Questions Set 1

Posted on :12-03-2016

Q1. Given the root of a binary tree containing integers, print the columns of the tree in order with the nodes in each column printed top-to-bottom.
Input:
      6
     /
    3   4
   /  
  5   1   0
 /     /
9   2   8
     
      7

Output:
9 5 3 2 6 1 7 4 8 0

Input:
       1
     /  
    2     3
   /   /
  4   5 6   7

When two nodes share the same position (e.g. 5 and 6), they may be printed in either order:

Output:
4 2 1 5 6 3 7
or:
4 2 1 6 5 3 7

Q2. Given an array and a number, add it in such a way where array is [0,0,1] and number is 4 output will be [0,0,5] 

Example 2 : 
array is [1] and number is 9 output will be [1,0]

Q3. Given a set of numbers {x1, x2, x3, x4, ..., xN} (N>=3) a set of its pairwise sums is {x1+x2, x1+x3, x1+x4, x2+x3,x2+x4,x3+x4, ...,}. (That is s_k = x_i + x_j where i != j) 
Restore a set of numbers given a set of its pairwise sums. 
Note: you dont know given some k, to which i and j it refers, (i.e. input is given in undefined order) 


EDIT: couldnt comment, so here is clarification 

Example:
S = {1, 5, 10, 100} (n elements)
P = {6, 11, 101, 15, 105, 110} (n * (n - 1) / 2 elements)
Given P you have to restore S. 
Note here means that if you knew which element in P corresponded to which pair of indices in S, you could just solve a simple linear equation
x1+x2=a{k1} x2+x3 = a{k2}, ...., x{n-1} + x{n} = a{k{n-1}, x{n} + x1 = a{k{n}}

Q4. Given a string where in each word letters were randomly shuffled and after that words were written without spaces (lets call it X). Also you have a dictionary. The task is to return all possible strings S that can be transformed into the string X and all words in S are from dictionary

Q5. Given two arrays/Lists (choose whatever you want to) with sorted and non intersecting intervals. Merge them to get a new sorted non intersecting array/list. 

Eg: 
Given: 
Arr1 = [3-11, 17-25, 58-73]; 
Arr2 = [6-18, 40-47]; 

Wanted
Arr3 = [3-25, 40-47, 58-73];

Q6. Task schedule: given a sequence of task like A B C(means 3 different tasks), and a coldtime, which means you need to wait for that much time to start next [same] task. Now---- 

Input: string, n 

Output: the best task-finishing sequence. 

eg. input: AAABBB, 2 
Output: AB_AB_AB 
( "_" represents do nothing and wait)

Q7. Given a decimal number, write a function that returns its negabinary (i.e. negative 2-base) representation as a string.
#!/usr/bin/env python3
assert solution(-15) == 110001
assert solution(2) == 110
assert solution(13) == 11101

Q8. Given a forest of balanced binary trees and two nodes, n1 and n2, find the closest common parent of n1 and n2. Nodes have parameters "parent", "left" and "right", and you cannot access the values of the nodes. If n1 and n2 are not on the same tree, return NULL. 

Try to do this in O(log(n)) time and O(1) space.

Q9. Given an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.

Q10. Given integer k and a subset S of set {0, 1, 2, ..., 2^k - 1} 
Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a) 
& here is bit-wise and. 
Do it faster than O((2^k)^2), assume k <= 16 

Example: 
0b111 
0b101 
0b010 

Answer: 2 

0b110 
0b011 
0b101 

Answer: 0

Q11. Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T. 
example: 
S=adobecodebanc 
T=abc 

Answer: banc

Q12. Given a set of ranges: 
(e.g. S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}. 
And given a target range R (e.g. R = (3, 13) - meaning the range going from 3 to 13). Write an algorithm to find the smallest set of ranges that covers your target range. All of the ranges in the set must overlap in order to be considered as spanning the entire target range. (In this example, the answer would be {(3, 9), (9, 12), (11, 14)}.

Q13. Given an array of positive integers (excluding zero) and a target number. Detect whether there is a set of consecutive elements in the array that add up to the target. 

Example: a = {1, 3, 5, 7, 9} 
target = 8 

output = true ({3, 5}) 

or target = 15 
output = true : {3, 5, 8} 

but if target = 6, output would be false. since 1 and 5 are not next to each other.

Q14. Given an array of integers. Modify the array by moving all the zeros to the end (right side). The order of the other elements doesnt matter.

Q15. Given a dictionary containing a list of words, a starting word, and an ending word, return the minimum number of steps to transform the starting word into the ending word. 

A step involves changing one letter at a time to a valid word that is present in the dictionary. 

Return null if it is impossible to transform the starting word into the ending word using the dictionary. 

Example

Starting word: cat 
Ending word: dog 

cat -> cot -> cog -> dog (cot and cog are in the dictionary) 

return 3

Q16. Given predicted stock prices for next n days for a stock e.g : 10, 30, 42, 15, 20, 50, 10, 25 find the maximum profit that can be made with a single buy-sell transaction. If no profit can be made return 0. In the example buying at 15 and selling at 50 gives maximum profit. Note that the two prices are neither minimum nor maximum in the array.

Q17. We have an array of objects A and an array of indexes B. Reorder objects in array A with given indexes in array B. Do not change array As length. 

example:
var A = [C, D, E, F, G];
var B = [3, 0, 4, 1, 2];

sort(A, B);
// A is now [D, F, G, C, E];

Q18. You are given a set of points on x axis (consumers) 
Also you are given a set of points on a plane (producer) 

For every consumer print the nearest producer. 
Wanted something better than O(n^2) time. 

Example: 
consumers: 1 5 7 
producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100) 

Answer
for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2) 

Follow-up question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm?

Q19. Given n, return 1 ^ 2 ^ 3 ^ ... ^ n 
Where ^ is binary xor. 
Note: n is a 64-bit number, and 1<<63 is a valid n for this problem. 

Examples:

>>> reduce(lambda a,b:a^b, [1,2,3])
0
>>> reduce(lambda a,b:a^b, [1,2,3,4])
4
>>> reduce(lambda a,b:a^b, [1,2,3,4,5,6,7])
0
>>> reduce(lambda a,b:a^b, [1,2,3,4,5,6,7,8,9])
1

Q20. Given an array of positive, unique, increasingly sorted numbers A, e.g. A = [1, 2, 3, 5, 6, 8, 9, 11, 12, 13]. Given a positive value K, e.g. K = 3. Output all pairs in A that differ exactly by K. 

e.g. 2, 5 
3, 6 
5, 8 
6, 9 
8, 11 
9, 12 

What is the run time for your code?

Q21. You are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3}; 
Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, k-th order statistic on slice [a:b] of arr. 
E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it - get [0,1,5] and take k-th element, that is - 5. 

Implement request(a, b, k) function. You can pre process input data, that is, assume there will be only one array and many request() calls.

Q22. Design Live comments. If your facebook.com homepage is open with bunch of feeds and if someone comments on those feeds, the comments should automatically show up in facebook.com home page without refreshing the page. Feeds could be a simple status update by a friend, post in a group, post by a person youre following, post in a page youve liked etc. 

Few things what they are looking for - 
1. How do you solve it initially and how do you scale it? 
2. How do you scale push model in-case if you choose PUSH model to solve it? 
3. If push cannot scale how do you solve it? 
4. How pull model solves it? 
5. When will you use push vs pull?

Q23. Write Program for String Permutations using most efficient algorithm. Can you solve problem in O(n) time ?

Q24. Conflict resolution in Multi Master systems.

Q25. Design a URL shortener service

Q26. Check a binary tree is a binary search tree

Q27. Write a function to check if a string matches a regex patter. Note that you only have to deal with patterns containing "*". Also, note that the pattern cant start with "*". 

Some examples: 
isMatch(“aa”,”a”) → false 
isMatch(“aa”,”aa”) → true 
isMatch(“aaa”,”aa”) → false 
isMatch(“aa”, “a*”) → true 
isMatch(“aa”, “*”) → true 
isMatch(“ab”, “*”) → true 
isMatch(“ab”, “*”) → true 
isMatch(“b*a”, “a”) → true 
isMatch(“a*a”, “a”) → true 
isMatch(“aab”, “c*a*b”) → true

Q28. Given an array of integer, find the maximum drop between two array elements, given that second element comes after the first one.

Q29. On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.

Q30. Find the in-order successor of a node in BST


  
   






FreshersLive - No.1 Job site in India. Here you can find latest 2016 government as well as private job recruitment notifications for different posts vacancies in India. Get top company jobs for both fresher and experienced. Job Seekers can get useful interview tips, resume services & interview Question and answer. Practice online test free which is helpful for interview preparation. Register with us to get latest employment news/rojgar samachar notifications. Also get latest free govt and other sarkari naukri job alerts daily through E-mail.

closepop
closepop