akira
 0of 0 votes
AnswersA bus has to travel from A to B and the distance is d miles. There are many gas stations between A and B.
 akira in United States
The bus has initially g gallon of gas in tank. 1 gallon of gas travels 1 mile.
Gas stations have inforamtion of remaining distance from station to destination b and max gas that can be filled from the station.
Find the minimum number of stops for bus without running out of gas ever.
eg: gas = 10 , distance = 20
gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}
o/p = 1
If bus stops at the stop{14,11} that is 14 miles away from destination and fills 11 gallon then it can reach destination with 1 gallon spare.
It can also stop as {16,3} and {10,7} but its 2 stops and at destination it runs out of gas.
Similarly {11, 5}, {7, 6} has 2 stops but has 1 gallon spare at destination. Report Duplicate  Flag
Microsoft Algorithm  1of 1 vote
AnswersGiven a list of characters, write a function to output a list of length of minimum non overlapping subsequences that can partition the input list.
 akira in United States
For example:
Input : [a,b,c]
Output: [1,1,1]
Explanation: There are no repeated characters.
Input : [a,b,c,a]
Output: [4]
Explanation: The 'a' is repeated so one subsequence is between a to last a.
Input : [a,b,c,b,a,e,b,a,d,f,g,d,f,i,f,k,l,m,n,m,l]
Output: [8,7,6]
Explanation: max length from 1st 'a' to last 'a' is 8.
1st 'f' to last is 6 adding d to it = 7
so on Report Duplicate  Flag
Amazon Software Developer Algorithm  0of 0 votes
AnswersRobot hand movement
 akira in United States
Given a (1) string message (consisting of only upper case alphabets), and (2) width of keyboard, output the movements required by an automated robot hand to print out the string message.
The robot hand can move right, left, up or down. It cannot move diagonally.
Ex 1:
String message: “HI”
Width: 26
Output: R8, T, R1, T
Ex2:
String message: “HELLO”
Width: 13
Output: R8, T, L3, T, R7, T, T, D1, L10, T Report Duplicate  Flag
Software Developer Algorithm  0of 0 votes
AnswerGiven a grid of M*N size and robot is sitting on the top leftmost corner (0,0) and has to reach the bottom right most corner (M1,N1). Robot can only move up, down, left or right and cannot move diagonally. Find the shortest path on the grid.
 akira in United States
Follow find total number of paths possible. Report Duplicate  Flag
Unity 3D Software Engineer / Developer  0of 0 votes
AnswersWrite a function to convert a String of ip address to hex
 akira in United States
eg: ip is 197.27.11.11 = 0xC51BBB. The conversion to hex has to be done without preexisting library function. like String.format() etc. Report Duplicate  Flag
Unity 3D Software Engineer / Developer Coding  0of 0 votes
AnswersAn web service maintains logs (suppose there are multiple log files per day) of all ip address which has requested service. If there is a DOS attack on the server find all ip addresses that has sent more number of requests and block them. Can this be done without writing any function in higher programming language?
 akira in United States
What would the function look like if written in some language like C, Java etc?
Can this be done in Time optimized and space optimized manner? Report Duplicate  Flag
Unity 3D Software Engineer / Developer Coding  1of 1 vote
AnswersA gaming application assigns a sessionid to each player every time they start a new session. These sessionid are all unique and can be selected from 1 to 10^6 numbers. A get() and put() function is used to assign and then release the sessionid for each user. A released session id can then be reused and assigned to another player. How can you write the get() and put() function to handle this in time and space optimized manner?
 akira in United States
I did provide o(n) solution with hash table but he seemed to be asking for a bit manipulation or bit masking technique for 32 bit address. Report Duplicate  Flag
Bit Manipulation  0of 0 votes
AnswersWrite a merger and separator for Linked List.
 akira in United States
eg: 1>2>3>4>5
separator()
1>3>5 and 2>4
merger()
1>2>3>4>5 Report Duplicate  Flag
Yahoo Software Engineer / Developer Data Structures  0of 0 votes
AnswersGiven a nonnegative integer n, check if it is possible to build a pyramid of '*' and empty spaces where first row has one '*' and second has three '*' and so on.
 akira in United States
For example
Input: n =4 Output: True
Explanation : The pyramid can be build
*
***
Input: n = 9 Output: True
Explanation : The pyramid can be build
*
***
*****
Input: n = 6 Output: False
Explanation : The pyramid cannot be build as last row will be incomplete
*
***
** Report Duplicate  Flag
Nutanix Software Developer Algorithm
ChrisK, Thank you for the answer. It explains a lot.
He actually did ask me the exact follow up. How to scale and distribute the application across several machine? How will it work if players are in geographically different locations?
What can be the best answer in this scenarios?
The given input array might contain both negative and positive integers. Therefore, the idea is use two pointers.
1) One pointer at the left end (low =0)and another pointer on the right end(high = arr.length1) index of array.
2)Resulting array of squares is filled from right to left (arr.length1 to 0) i.e largest square to smallest square.
3)Compare the absolute value of the element pointed by the two pointers whichever is greater the result array takes the square of that element.
4)Every element in the array is processed at least once
Time Complexity : O(n)
Note : But the key here is that when an large integer is squared it might overflow the integer bounds. So either a custom class to handle that situation or Long or BigInteger class in java should be used to handle that.
The below code is not doing that but is rather a simple method to do the required.
public class GetSortedSquares {
public static void main(String[] args) {
int[] arr = {6,3,2,3,4};
int[] arr1= {1,2,3,4};
int[] result = getSortedSquares(arr);
int[] result1 = getSortedSquares(arr1);
printArr(result);
printArr(result1);
}
// The function to get the Squares in Sorted order
private static int[] getSortedSquares(int[] arr) {
int[] result = new int[arr.length];
int low =0 , high = arr.length1, i = arr.length1;
while(low <= high && i >= 0){
if(Math.abs(arr[low]) >= Math.abs(arr[high])){ // absolute value of array element on the left is greater than the array element on right
result[i]= arr[low]*arr[low];
i;
low++;
}else if (Math.abs(arr[low]) < Math.abs(arr[high])){
result[i]= arr[high]*arr[high];
i;
high;
}
}
return result;
}
private static void printArr(int[] result) {
for(int n : result)
System.out.println(n);
}
}

akira
October 20, 2017 Open Chat in New Window
1) One can sort the array and then get the three largest from the end of the array. But this will be O(nlogn) solution depending on the sorting technique used.
2) Initiate first, second and third element with MIN_Value. Compare each element with the first ,second and third element as we move along the array.
Time Complexity : O(n) Space Complexity : O(1)
 akira November 04, 2017