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 Indiadef 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