Thursday, March 5, 2015

ION trading Java Interview Questions

Design Questions
1. Design high throughput trading application? Application is hosted in NY and we have traders all over the world accessing this application. What things we need to take care on designing this application.
Hint- High concurrency using Atomic package rather than synchronization, Timezone and Localization, Currency Conversion, Connection Pooling, No GC pauses (proper memory management), Horizontal scalability using restful architecture, ActiveMQ for asynchronous communication, etc.
2. If we have unsorted list of numbers like 3,1,4,7,9,4,7,4,9 best way to figure out if number n exists in the list? they were interested in constant time performance ?
Hint - Consider preprocessing the data using a hashtable and then query the table in O(1) complexity
3. Removing duplicates from unsorted list of integer maintaining the order of input in results? if you have unsorted list of
0,5,9,5,6,7,6,9
the result should be
0,5,9,6,7 and the performance should be best over more number of elements.
Hint - Store the list in LinkedHasSet and printing it will get expected output, Other way could be use of hashtable to store the numbers and then printing it, Counting Array can also be used to achieve the same if the input range is known and limited.
4. Describe the design of a low latency distributed environment where multiple processes( or threads) need to access shared data structure or a database for a fast ( speaking of a fraction of a milisecond) read or update. You have to process tons of request very quickly ( you can think of market price data as an example, etc). How would you build such an environment in the most efficient way? Describe the solution in details(a few sentences).
Hint- use of non-blocking algorithms and CAS (compare and Set/Swap) feature provided by java. This way we will get rid of the low throughput offered by synchronization used in thread safe programs. refer to Concurrency in practice for more details.
5. Write a program to print elements of a linked list in reverse order by using same single linked list in java.
Hint - Start traversing the singly linked list and put the nodes in a stack till you reach the end of the list. Then pop from the stack. The elements will be in the reverse order to the original linked list.
6. Design a thread-safe ObjectPool (Generic type i.e. ConnectionPool, ThreadPool, etc) in Java. Interface should look like -
interface Pool {
Connection get();
void put(Connection con);
}
Hint- Designing a thread-safe connectionPool in java
7. Describe the Producer Consumer problem using Java language ? How will you make it thread-safe ?
8. Given a huge file, design a data structure to output all possible anagrams of a particular word. For Eg the file contains: "POT, OPT, TOP". If I query for POT, I should get back all possible anagrams contained in the file.
9. Write a Java program to reverse the sequence of words in a sentence. for example "This is my world" should become "world my is this"
Hint -
With limited Space -
This can be done without any additional space in 2 pass
1) reverse the string in place
2) reverse each word of the reversed string.
With Time : O(N) and Space : O(N)
Split the words and then traverse the array in reverse direction.
10. Print n elements of a fibonacci series.
11. Find whether there is a loop in a given linked list or not ?
Hint - It can be done using one pointer but not without extra space. You can store the addresses of all the nodes visited in a hashmap. And for every next node, check its presence in hashmap.

Goldman Sachs Java Interview Questions

1. There is a String array String[] words = {"hello", "world", "HELLO", WORLD"}; How will you print output like hello-2, world-2 i.e. word followed by its count ignoring the case of the words in the input Array ?
2. There is a array of words String[] words = {"abc","bca", "cab", "cba", "def", ...} etc. So if given an input "cab", your program should print all the words that contains 'c', 'a' and 'b' i.e. "bca", "abc", "cba", etc. How will you achieve that ? Anagrams example ?
3. How will you implement your own hashmap in Java ? How will you handle collision of keys ? Basically interviewer wants to know internals of a hashing data structure.
4. How will you implement multiplication for very big numbers without using Java inbuilt classes ?
5. Given an input string, write a function that returns the Run Length Encoded string for the input string. For example, if the input string is “yyyybbbbdexxxxxxx”, then the function should return “y4b4dex7″.
6. Given a string check if the string is palindrome or not ?
7. What are the main interfaces in Java Collections framework ? What is difference between Set and List ?
8. Let's say I gave you a long String and I wanted you to tell me the most common word in that String. How would you do that?
follow-up: OK, how would you estimate the size and time complexity of this solution? How would you estimate the ACTUAL size usage? (Hint: how many words are in the English language? Would having a dictionary in front of you help?)
follow-up #2: OK, how about if I gave you the entire works of Alexandre Dumas, one of the most prolific authors in history. How would your solution work? How could you change it to solve this more specific problem?
follow-up #3: Now, what if we wanted to find the most common PHRASE in his writings. (Upon clarification, the interviewer wouldn't give a specific length, so I clarified to finding as long as a common 10 word phrase, because anything longer is unlikely.)
Hint - Find Top X occurring words in a very big file using Min-Heap and Hashtable.

9. why strings are immutable ? how many objects will be created in String temp = "A" + "B" + "C" ; explain your answer in detail.
Hint- Role of Immutable Objects in writing thread safe scalable applications.

10. You have 5 data sources. There is a program which calls these data sources and returns a count value. You need to speedup this program. How do you do that? This is a sample code
int count = getCount(ds1);
if(count < 100 )
count = count + getCount(ds2);
if(count < 100)
count = count + getCount(ds3);
if(count < 100)
count = count + getCount(ds4);
if(count < 100)
count = count + getCount(ds5);
Hint - Interviewer must be looking for multi-threading. Fetch count from all sources in parallel. Bonus points: If machine has less than 5 cores (for 5 data sources), say 4 cores, prioritize so that first 4 cores get the highest priority. Not sure how to do this in code.

11. How would one design a multi format converter that supports reading data from multiple data sources(web service, local disk, etc.). The data from the sources can be in multiple formats. The reader for each format may be different and how does one serialize this abstract data to multiple formats like image, xml etc. New readers, writers and data sources can be added later during implementation.
Hint- Design Patterns problem, look for java.io.* classes for example Reader, InputStream, etc. Decorator Design pattern. There are two variables here - 1. Multiple Datasources with common interface 2. Multiple formats with common interface. 9implementation can be provided later on. our APi should be coded over interface rather than implementation.

12. How will you reverse a linked list in Java ?
13. How will you find common ancestor of two given nodes A and B in a binary Tree ?
14. How reverse key index helps in faster data reading and what is use case for this? Complexity of B tree index?