## Facebook Placement Papers

Facebook Interview Questions Set 5

Facebook Interview Questions Set 4

Facebook Interview Questions Set 3

Facebook Interview Questions Set 2

Facebook interview Questions for Software Engineer

Facebook Tough Interview questions

## 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 don**

**t 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**

**: the best task-finishing sequence.**

__Output__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**

**: 2**

__Answer__0b110

0b011

0b101

**: 0**

__Answer__**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**

**: banc**

__Answer__**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**

## Top Companies Placement Papers

TCS Papers

Wipro Papers

HCL Papers

IBM Papers

Amazon Papers

CISCO System Papers

Cognizant Papers

CSC Papers

Tata Motors Papers

Tech Mahindra Papers

L&T Papers

Facebook Papers

Dell Papers

L & T Infotech Papers

Capgemini Papers

HP Papers

Microsoft Papers

Google Papers

Samsung Papers