## Deshaw Inc Interview Questions

- 0of 0 votes

AnswersYou are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

- Nits January 30, 2020 in India| Report Duplicate | Flag | PURGE

Deshaw Inc Tech Lead - 0of 0 votes

AnswersThe original question can be found from here :

- NoOne October 25, 2016 in India

franklinchen.com/blog/2011/12/08/revisiting-knuth-and-mcilroys-word-count-programs/

Read a file of text, determine the *n* most frequently used words, and print out a sorted list of those words along with their frequencies.

In the same spirit of the history:

1. Do it using pure shell scripting

2. Do it in the favourite language of your choice

Try to minimise code and complexity.| Report Duplicate | Flag | PURGE

Deshaw Inc Software Developer Algorithm - 0of 0 votes

AnswersApparently DESCO asked it. It was faulty, and I am fixing it. The physics was wrong. A mono pole is an abstract magnet with either the north or the south pole of the magnet.

[ en.wikipedia.org/wiki/Magnetic_monopole ]

Imagine you are given such *n* monopoles, all of the same type, say North type. Thus, all of these repel one another. The force of repulsion follows inverse square law :

[ en.wikipedia.org/wiki/Inverse-square_law ]

That is, given two such monopoles with a distance *r* between them, the force of repulsion between them is given by :`F = ( 1.0 ) / ( r ** 2 )`

Now, suppose you are also given an array of *n* number of positions over X axis, like : [ 0, 1, 4, 10 , 21 , .. ] where you need to place the monopoles ( imagine they are hold tight there, and do not move away ).

- NoOne October 18, 2016 in United States

After placement, you are given another monopole, of different type S, say. Find positions to place the monopole so that it is stable.

Fixes from the original question :

[geeksforgeeks.org/d-e-shaw-interview-experience-set-19-on-campus/ ]

1. Monopoles exhibit inverse square law, not inverse law.

2. It is impossible to have stable configuration using same type monopole, so one must use another type, repulsion is not stable, attraction is.

( Terrible physics mistakes )

PS. Do not try to do binary search here. Binary search assumption is underlying linearity of the structure, thus, effectively there are proportionate elements in left and right. In the classic cases of sorted array, the expectation is 50/50. But here due to non linearity (inverse square) , it won't work.| Report Duplicate | Flag | PURGE

Deshaw Inc Software Developer Algorithm - 0of 0 votes

AnswersGiven a convex polygon ( is planer as opposed to a polytope) and a point one had to tell if the point lies inside the polygon or outside the polygon.

- NoOne October 14, 2016 in India

To understand convexity : mathopenref.com/polygonconvex.html

Thus the question comprise of 3 sub problems :

1. How to store a polygon.

2. How to define inside and outside of a polygon.

3. How to solve the actual one, given 1,2 ?| Report Duplicate | Flag | PURGE

Deshaw Inc Software Developer Algorithm - 0of 0 votes

AnswersAs you guys know, C did not have,and does not have anything called class. C++ has them. Now, C++ was written using C. In fact, C++ initially was called C with classes.

- NoOne October 14, 2016 in India

Thus, here is the problem for you.

Given you have C, and you need to implement class like behaviour, how you would do it? Specifically, implement the following in C :

1. A Simple Hello class with hello() function printing "Hello, World" .

2. A new operator which enables creating this constructor less class.

3. A delete operator that deletes the pointer.

How would you do it?| Report Duplicate | Flag | PURGE

Deshaw Inc SDET C - 0of 0 votes

AnswersImagine there are brick boulders, all of integer size.

Their sizes are stored in an array.

The figure looks something like this :

peltiertech.com/Excel/pix2/Histogram2.gif

Now, suppose someone is pouring water into it till water starts spilling.

You have to answer how much water the boulders are holding up.

- NoOne October 14, 2016 in India`def water_holding( arr ) { /* answer this */ }`

| Report Duplicate | Flag | PURGE

Deshaw Inc SDET Algorithm - 2of 2 votes

AnswersGiven an array of numbers, find the maximum and minimum sum of sub sequences at a distance > m

- nitinsharma021 July 25, 2016 in India

Example –

arr = {3, 4, -2, 1, -2, 4, 6, -3, 5} & m = 2

Solution – max = 13 {4 + 4 + 5}, min = -5 {-2-3}| Report Duplicate | Flag | PURGE

Deshaw Inc Algorithm - 2of 2 votes

AnswersGiven an array arr[] of size n. Three elements arr[i], arr[j] and arr[k] form an inversion of size 3 if a[i] > a[j] >a[k] and i < j < k. Find total number of inversions of size 3

- tihor December 29, 2015 in India

e.g.

Input: 23, 10, 24, 7, 12, 19

Ans: 23, 10, 7| Report Duplicate | Flag | PURGE

Deshaw Inc Applications Developer - 2of 2 votes

AnswersGiven an Integer where only one Bit is set, Identify that Bit in O(1).

- Enkesh Gupta July 11, 2015 in United States| Report Duplicate | Flag | PURGE

Deshaw Inc - 0of 0 votes

Answerscommand which will tell all the running process and amount memory consumed by them

- poojaarora014 February 22, 2015 in India| Report Duplicate | Flag | PURGE

Deshaw Inc SDET Unix - -2of 2 votes

AnswerGarbage collection in java

- poojaarora014 February 22, 2015 in India| Report Duplicate | Flag | PURGE

Deshaw Inc SDET Java - 0of 0 votes

Answersfind the max length of name(1stName+2ndName+MiddleName) table value.

- poojaarora014 February 22, 2015 in India| Report Duplicate | Flag | PURGE

Deshaw Inc SDET SQL - 0of 0 votes

AnswersIf problem Statement "sun is rise in west " !

- Dext...... December 18, 2014 in India

?

How to do tester test it ? What are all possible solution ?| Report Duplicate | Flag | PURGE

Deshaw Inc Testing - 1of 1 vote

AnswersImplement data structure for garbage collector in java

- shrey.chaturvedi2525 December 23, 2013 in India| Report Duplicate | Flag | PURGE

Deshaw Inc SDE1 Java - 0of 0 votes

Answerswrite a function to generate a random number in a given range.

- nagyuga October 19, 2013 in India

Condition:

Each number should be generated exactly n times, i.e., if each number has to be generated only 5 times and

the number 7 has already occured 5 times then your function should not generate 7 again.

Actual he asked question linking with array but it is bit confusion, he asked to do the above only| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Algorithm - 0of 0 votes

Answersthere is a stock comp whose stock prices are known to u of next 365 days. u have to write the code on which day u should buy how much stokes and sell how much stock. U cannot sell a stock until u havnt bought ny stock. write o program to optimise the profit...

- homework August 05, 2012 in India| Report Duplicate | Flag | PURGE

Deshaw Inc Algorithm - 0of 0 votes

AnswersWrite a program to find the longest increasing sub sequence of a given array

- samant.bit July 20, 2012 in India| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Algorithm - 2of 2 votes

AnswersRound 1: Q2:

- Abee July 20, 2011

Puzzle

Given 25 horses, find the best 3 horses with minimum number of races. Each race can have only 5 horses. You don't have a timer.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Brain Teasers Highbridge Capital Deshaw Inc - 1of 1 vote

AnswersWrite an algorithm to find the absolute max subsequence of an array containing both positive and negative numbers in O(n) time

- Yashanth August 19, 2010

Eg: {100,-2,300} sum=398

{1,2,3,-9} sum=9

{1,2,3,-4} sum=6

{-1,-2} sum=3| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Arrays - 0of 0 votes

Answersfind maximum length BST in a given binary tree.

- ajay July 27, 2010| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Trees and Graphs - 0of 0 votes

AnswersInput integer iIn is given as input.

- furious_coder July 07, 2010

Output is also an integer iOp.

The string must contain only the following characters.

'A' and

'B'

The string formation must follow these rules.

1. The number of A's and B's in the string are equal.

2. For any prefix of the string, the number of A's must be greater than or equal to

the number of B's.

Given iIn, then find the number of possible string which match this criteria iOp.

Eg,

AB

ABAB

AABB

AAABBB

ABABAB

AABBAB

...

Any suggestions towards solving this question is welcome.

A Brute force method can solve the problem.

But when the input becomes larger, the algorithm might eventually get slow. So a better solution is to be

suggested.| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Algorithm - 0of 0 votes

AnswersInput : Two sorted arrays, elements of both sorted in decreasing order : A and B.

- Amay Singh June 07, 2010

Output : A matrix C with (a,b,sum) such that aEA, bEB, sum = a+b and in decreasing value of sum.

Complexity required : O(n)| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer - 0of 0 votes

AnswersFind the largest palindrome in a given string.

- kunalnitin June 03, 2010| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Algorithm - 0of 0 votes

AnswersTwo cops and a robber are located on opposite corners of a cube and move along its edges. They all move at the same rate. Is it possible for the cops to catch the robber.

- pluristiq April 10, 2010

[Each of the 3 people can see each other at all times and can react instantaneously to each others movements. Stopping is allowed.]| Report Duplicate | Flag | PURGE

Deshaw Inc Analyst - 0of 0 votes

AnswersYou have a collection of marbles of different colors.U have many boxes with u which contain marbles of the same color.Ur younger brother has played with the marbles and scattered them randomly.Write an algorithm to arrange the marbles in the boxes in such a way that each box contains the marbles of the same color.The algo should be optimum in time and space respectively.

- TOPCODER December 28, 2009| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Algorithm - 1of 1 vote

AnswersWrite a program to generate all the possible magic squares of order N*N where N is odd.A magic square is one in which the sum of all the rows,columns and diagonals is the same

- Pramodh September 11, 2008| Report Duplicate | Flag | PURGE

Deshaw Inc Development Support Engineer Algorithm - 0of 0 votes

AnswerS = {Si, i=i,I} Set S has I elements

- Lee June 04, 2008

P = {Pj, j=1,J} Set P has J elements

Q = {Qk, k=1,K}, Set Q has K elements

Define a unique mapping F = {Si, Pj} ? {Qk} for some i, j, k.

Find the following mapping pairs {Si, Pj} ? {Qj} where i’s are unknown and j= m1, m2 where m1 and m2 are given.

Is it possible to find a polynomial time subset R of S (say i=r1,r2 where r2-r1 = r, i.e. of size r) that is guaranteed to include all of above Si’s.| Report Duplicate | Flag | PURGE

Deshaw Inc Financial Software Developer Algorithm - 0of 0 votes

AnswersYou have a cube that is painted red on all 6 sides. If you were to make two symmetrical cuts in each dimension, you would have a total of 27 pieces. How many pieces have red on all 4 sides, on 3 sides, on 2 sides, on 1 side and on no sides?

- Koonz February 14, 2008

Heres the best way I can explain the cut in one dimension:

=============

| 1 2 |

| 1 2 |

| 1 2 |

| 1 2 |

=============

where the vertical '1' and '2' lines are the cuts so now you have three pieces. So imagine that in every dimension.| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Brain Teasers - 1of 1 vote

AnswersDesign an algorithm to find whether a given string is formed by the interleaving of two given strings or not.

- Aditya December 07, 2007

s1= aabccabc

s2= dbbabc

s3= aabdbbccababcc

Given s1,s2,s3 design an efficient algorithm to find whether s3 is formed from the interleaving of s1 and s2.| Report Duplicate | Flag | PURGE

Deshaw Inc Financial Software Developer Data Structures Coding Algorithm - 0of 0 votes

AnswersThere is a circular track.

- Saravana Madhusudhan B July 15, 2007

There are n gas stations of capacity ci.

To go from one station to the next station it takes certain amount of gas gi.

For any station the gas available may not be enough to get to the next station.

Write a linear time algorithm to find the correct station in which we must start in order to complete one round around the track.| Report Duplicate | Flag | PURGE

Deshaw Inc Software Engineer / Developer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.