xankar
BAN USER- 0of 0 votes
Answers1) Given a file containing lines of chars, find if it contains "aaaaab\naaaaa" string pattern. Need to return true only if contains the EXACT pattern specified (observe the new line character).
- xankar in United States
2) How do you differentiate between actual new line and the new line character?
3) what if the file is way too big to bring it all in memory?| Report Duplicate | Flag | PURGE
Dropbox Backend Developer Algorithm - 2of 2 votes
Answers/**
* Given a nested list of integers, returns the sum of all integers in the list weighted by their REVERSED depth.
* For example, given the list {{1,1},2,{1,1}} the deepest level is 2. Thus the function should return 8 (four 1's with weight 1, one 2 with weight 2)
* Given the list {1,{4,{6}}} the function should return 17 (one 1 with weight 3, one 4 with weight 2, and one 6 with weight 1)
- xankar in United States*/ public int reverseDepthSum (List<NestedInteger> input) { // implementation here }
| Report Duplicate | Flag | PURGE
Linkedin Backend Developer Algorithm - 0of 0 votes
Answers
- xankar in United Statesimport java.time.Duration; import java.time.LocalTime; import java.util.List; import java.util.Map; // Your goal is to write business logic for a very simple Restaurant booking system // You are encouraged to refactor exisiting code, create other classes, write helper methods etc // You also need to make sure that the implementation works correctly class Reservation { public String name; public int partySize; public LocalTime startTime; } class Table { public int tableNumber; public int maxPartySize; } class Restaurant { public List<Table> tables; public LocalTime openTime; public LocalTime closeTime; public Map<Integer, Duration> reservationDurationsPerPartySize; // Returns a Table if Reservation could be booked, null otherwise // Booking rules: // 1) Reservation could be made only when the Restaurant is open. // 2) Only one Reservation can be seatted a Table at any time. // 3) Reservation can be seatted only at a Table of the same or a bigger size. // 4) Reservation should stay on the same Table for the whole Duration. // 5) Reservation Duration is determined by PartySize. public Table bookReservation(Reservation reservation) { //TODO: } }
| Report Duplicate | Flag | PURGE
Opentable Backend Developer Algorithm Data Structures Java Problem Solving - 0of 0 votes
Answers1) Finish writing the below method: bookReservation(Reservation reservation)
2) You are free to add, modify, etc the following classes and method
- xankar in United Statesimport java.time.Duration; import java.time.LocalTime; import java.util.List; import java.util.Map; // Your goal is to write business logic for a very simple Restaurant booking system // You are encouraged to refactor exisiting code, create other classes, write helper methods etc // You also need to make sure that the implementation works correctly class Reservation { public String name; public int partySize; public LocalTime startTime; } class Table { public int tableNumber; public int maxPartySize; } class Restaurant { public List<Table> tables; public LocalTime openTime; public LocalTime closeTime; public Map<Integer, Duration> reservationDurationsPerPartySize; // Returns a Table if Reservation could be booked, null otherwise // Booking rules: // 1) Reservation could be made only when the Restaurant is open. // 2) Only one Reservation can be seatted a Table at any time. // 3) Reservation can be seatted only at a Table of the same or a bigger size. // 4) Reservation should stay on the same Table for the whole Duration. // 5) Reservation Duration is determined by PartySize. public Table bookReservation(Reservation reservation) { //fill this method }
| Report Duplicate | Flag | PURGE
Google Backend Developer Software Design - 1of 1 vote
AnswersYou have two servers. Both of these servers have an identical file with billion characters except for one single character. These servers are connected over a very slow connection.
- xankar in United States
How do you find the different character?
My ans: split those files in to batches of characters of 10,000 (say), now calculate checksum and compare the checksums for the chunks of 10,000 character lines. So now you are just comparing 'ints' and not the files per say. (remember the connection is very slow)
His question: How do you optimize this?| Report Duplicate | Flag | PURGE
VMWare Inc Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersWrite a program that takes an integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if your output contains 4 * 3, you should not print out 3 * 4 again as that would be a repeating set. Note that this is not asking for prime factorization only. Also, you can assume that the input integers are reasonable in size; correctness is more important than efficiency.
- xankar in United States
Eg: PrintFactors(12) 12 * 1 6 * 2 4 * 3 3 * 2 * 2| Report Duplicate | Flag | PURGE
Linkedin Software Developer Algorithm - 0of 0 votes
Answers/*
- xankar in United States
Prison cell question
In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbors." A wall with a window separates adjacent cells, and neighbors can communicate through that window.
All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbors find out, and each communicates this to his other neighbor. That prisoner passes it on to his other neighbor, and so on until they reach a prisoner with no other neighbor (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.
Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.
Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.
Task: find the minimum amount of gold we need to bribe the prisoners so that the chosen prisoners can be released without causing cell destruction.
Input example:
8 cells, 1 prisoner has to be released. The prisoner to be released is the 3rd one.
|1|2|3|4|5|6|7|8|
7 gold coins
another example:
20 cells, 3 prisoners to be released: 3, 6 and 14
|1|2| |4|5| |7|8|9|10|11|12|13| |15|16|17|18|19|20|
release prisoner 3: 19 gold coins
release prisoner 6: 16 gold coins
release prisoner 14: 13 gold coins
release 14: 19 gold coins
release 6: 12 gold coins
release 3: 4 gold coins
input:
number of cells
prisoners that need to be released
output:
least number of gold coins we need to give
*/| Report Duplicate | Flag | PURGE
Amazon Software Developer Brain Teasers - 2of 2 votes
AnswersWrite a method to count the number of 2s between 0 and n.*
- xankar in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Coding - 0of 0 votes
AnswersDesign an algorithm to figure out if someone has won in a game of tic-tac-toe.
- xankar in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Coding - 0of 0 votes
AnswersDesign a hashMap in Java. Implement put, get, remove, resize methods.
- xankar in United States| Report Duplicate | Flag | PURGE
Uber Software Developer Algorithm - 0of 0 votes
AnswerDesign a Twitter feeds API. How would you actually connect it from a mobile? What happens behind the Twitter network? how do the Trends get published? From where does Twitter get the information for a particular trend(Eg: #Obama, #nfl) and publish it out? What protocol does it use? How do you connect to Twitter API? How does Twitter handle multiple connections?
- xankar in United States| Report Duplicate | Flag | PURGE
Uber Software Developer Software Design - 0of 0 votes
AnswersGiven a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
- xankar in United States
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".| Report Duplicate | Flag | PURGE
Uber Software Developer Algorithm - 1of 1 vote
AnswersWAP to take one element from each of the array add it to the target sum. Print all those three-element combinations.
- xankar in United States
/*
A = [1, 2, 3, 3]
B = [2, 3, 3, 4]
C = [1, 2, 2, 2]
target = 7
*/
Result:
[[1, 2, 4], [1, 3, 3], [1, 3, 3], [1, 3, 3], [1, 3, 3], [1, 4, 2], [2, 2, 3], [2, 2, 3], [2, 3, 2], [2, 3, 2], [3, 2, 2], [3, 2, 2]]| Report Duplicate | Flag | PURGE
Uber Senior Software Development Engineer Algorithm - 0of 0 votes
AnswerLet's say you have a fixed thread pool of size 1, internally how does this threadPool work? How is that the same thread gets used again and again.
-------
My answer: The run() methods from various classes are loaded on to a task Queue. As and when the tasks get added to to this queue, the thread keeps on acting on this queue.
Something like:
Queue qTask = new Queue();
qTask.enqueue(object1.method1());
qTask.enqueue(object2.method2());
...
- xankar in United Statespublic void run(){ while(true){ if (qTask == null or empty){ wait() } //Take tasks out of qTask }
| Report Duplicate | Flag | PURGE
Java - 0of 0 votes
AnswersWhat are the disadvantages/limitations of a ConcurrentHashmap in JAVA?
- xankar in United States| Report Duplicate | Flag | PURGE
Java - 0of 0 votes
AnswersGiven a huge file, design a data structure to output all possible anagrams of a particular word.
- xankar in United States
For Eg the file contains: "POT, OPT, TOP"
If I query for POT, I should get back all possible anagrams contained in the file.
--| Report Duplicate | Flag | PURGE
Goldman Sachs Senior Software Development Engineer Data Structures - 0of 0 votes
AnswersYou have two sorted list A and B.
- xankar in United States
A = [1, 3, 4, 6,8,10, 17, 34]
B = [2, 8, 17, 33, 44, 66, 89, 100, 123]
Write a program to print those numbers which are
1) in A and not in B
2) in B and not in A
Eg: After print: 1 , 3 , 4 , 6 , 10, 33, 34, 44,, 66, 89, 100, 123
I was asked to write this in JAVA.| Report Duplicate | Flag | PURGE
Morgan Stanley Senior Software Development Engineer Algorithm Java - 1of 1 vote
AnswersIn a series of 1 to N, two numbers are missing. Find the missing numbers? Quickest way?
- xankar in United States| Report Duplicate | Flag | PURGE
Amazon Algorithm - 3of 3 votes
AnswersCoding:
Public void TransferAccount(AccountID id1, AccountID id2){ Account a1 = id1.GetAccount(); Account a2 = id2.GetAccount(); //Swap amounts. Temp = a1.Balance; a1.Balance = a2.Balance; a2.Balance = Temp; }
Q1: How do you make it thread safe?
I said use “public void synchronized” Good. But terrible performance since the entire method is synchronized.
Q2: Can you not lock on the entire method? I said used nested locks:Synchonized(a1) Synchronized(a2) { //swap }
His q: This will lead to a deadlock if in another thread I call Transfer (id2, id1) and Transfer (id1, id2).
Synchonized(a1) Synchronized(a2) { //swap }
Synchonized(a2) Synchronized(a1) { //swap }
How do you prevent this then? How do you design your code to not to get in to deadlock? (stumbled here)
- xankar in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Java Threads - 0of 2 votes
Answers3) Coding question:
public class ThreadingQuestion extends Thread { public static void main(String[] args) { public static boolean flagRun = true; new thread { void run(){ while (flagRun) //do something }.start() flagRun = false; }
Will the thread spawned will ever see the flagRun=false?
- xankar in United States
My corrected answer after a couple of attempts: No, since each thread will get a copy of it’s own flagRun, changing the flagRun value in the main thread will not be seen in the spawned thread.
How to fix it: declare flagRun to be volatile so that the values can be changed and seen in either threads.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Java - 1of 1 vote
AnswersWhat is difference between "volatile" and "static volatile"? Give an example
- xankar in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Java - 0of 0 votes
AnswersCoding: Write a Client/Server. Three methods are given. Msg.Get(), Msg.Process(), Msg.Send(). Write code. Since Msg.Get() and Msg.Send() has to send messages over the network. It takes a lot more number of threads. So how many threads out of 10, would allocate to each of the three processes. What is the proportion?
- xankar in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Threads - 0of 0 votes
AnswersPuzzle: There are 5 slots(1,2,3,4,5) and 5 people(A,B,C,D,E). Each of them provide their preferences. A=1, B=2, C=3, D=4, C=4. Given an arbitary starting sequence say BCDEA, going clock wise: how many passes does it take to fill in those slots so that max number of people are happy. People are happy if A gets 1, B gets 2, C gets 3, etc. Remember D and E cannot be kept happy together at the same time because both of them prefer Slot-4.
- xankar in United States
My answer: Worst case scenario when you start at BCDEA(only E is happy because E comes in 4th position and prefers 4), next rotation pass CDEAB(no one is happy), DEABC(no one), EABCD(no one), ABCDE(4 people are happy). So for N people, it takes N passes.
His question: Can you do better than N passes? (Can you do this in less than N passes?)
(I tried to come up with something but stumbled.)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow do you add up a very long list of numbers multiple threads (100 threads?) How many cores do you require?
- xankar in United States
How do you increase the performance of this program? Does the number of threads created get limited by the cores of the box? How exactly are you gonna delegate it to the cores? (as in- these number of threads need to use core#1, and so)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
"Sathyaa blackhat" has the answer here:
stackoverflow.com/questions/4705069/c-program-on-reversing-a-sentence
Steps
1) Create a Reverse(start,end) method which reverses chars from start to end.
2) Then do Reverse (start, strlen-1). Reverse the whole string.
3) Then Reverse words by adjusting pointers until you encounter " ".
I found a similar question on stack overflow:
stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe
We can solve Q2 by summing both the numbers themselves, and the squares of the numbers.
We can then reduce the problem to
k1 + k2 = x
k1^2 + k2^2 = y
Where x and y are how far the sums are below the expected values.
Substituting gives us:
(x-k2)^2 + k2^2 = y
Which we can then solve to determine our missing numbers.
Example:
NumN: 1, 2, 3, 4, 5
Let's say 3 & 4 are missing (x and y)
ListN : 1, 2, 5
x + y = 7 -- (1) // SumOfNumN - SumOfListN
x^2 + y^2 = 25 -- (2) // (sumOf the squares in NumN) - (sumOf the squares in ListN)
Substitute (1) in (2),
x^2 + (7 - x)^2 = 25
Roots: 3, 4 which are the missing numbers
Not really.
My answer was: Assign each number to a treemap slot, iterate through the treemap using "iter" and simultaneously have counter from 0. If [iter.next() != counter]. Print that number as missing and do an ++counter if you find counter==inter.Next() else dont increment.
List<int> numbers = new List<int>();
//populate with the missing numbers
//etc
Treemap<int,int> treenum = new Treemap<int,int> ();
for(int num : numbers)
{
treenum.put(num,1);
}
int counter=0;
for(Entry<int,int> entry : numbers.entrySet()){
if(entry.getKey() == counter) {
counter++;
continue;
}
logger(Missing number is: counter;)
//Dont increment counter now
}
Is there a clever way of not using any sort of mapping?
- xankar March 16, 2013Forget it, I figured it out.
1) When you are using "=" when initializing a class, then always copy constructor is called.
Eg: Someclass b = a;
2) When you are using "=" to assign to an already initialized class, then assignment operator is called.
Eg: b = a or c = a.
Nice so far. In your code, you assigned map2= map1 for duplication, What if keys in map1 and map2 have some different keys? Like create map1 and map2 such that the key are map1_keys={john, chethan, flick, akkan} and map2_keys={john, twitter, flick,dan}, then you will have to iterate over map2 too, right?
How can you combine iterating both map1 and map2 efficiently and finally finding out the difference?
Can you pls walk through the code?
- xankar September 27, 2014Quantity, Influx, etc?