Below questions were asked to me during Expedia Gurgaon interview over Video call -
Round1 by Pushpendra:
1) Given a list of words, group them by anagrams
Input: List of "cat", "dog", "god"
Output: A Set of Sets of anagrams: {{'cat'}, {'dog', 'god'}}
3) Consider adding some additional tests in doTestsPass().
4) Implement the AnagramSolution group() method correctly.
5) If time permits, try to improve your implementation.
dog -> dgo -> {dog}
god -> dgo -> {dog, god}
I missed the last sample so couldn't write the improved version in first time, but was able to think of that approach during coding & interviewer also guided in resolving certain syntactical issues. Then I was able to write the below code after some modifications & corrections -
Note - If you try this problem using lambdas, you can do it in 5-6 lines, but again you need to be aware about those many APIs.
Round1 by Pushpendra:
1) Given a list of words, group them by anagrams
Input: List of "cat", "dog", "god"
Output: A Set of Sets of anagrams: {{'cat'}, {'dog', 'god'}}
3) Consider adding some additional tests in doTestsPass().
4) Implement the AnagramSolution group() method correctly.
5) If time permits, try to improve your implementation.
dog -> dgo -> {dog}
god -> dgo -> {dog, god}
I missed the last sample so couldn't write the improved version in first time, but was able to think of that approach during coding & interviewer also guided in resolving certain syntactical issues. Then I was able to write the below code after some modifications & corrections -
Note - If you try this problem using lambdas, you can do it in 5-6 lines, but again you need to be aware about those many APIs.
Round 2 by Digvijay:
Question 1: You have a website & you want to know the number of hits made in last 5 seconds. Even a user refreshes the
page, it will be considered a new hit. What approach you will take for this?
Answer I gave : I will keep a file for each user having the timestamp of each hit made by that user. And when required, I will
check all the files to calculate the hits in last 5 seconds based on current timestamp. But it will be slower, so I
suggested later to use some in memory database like Redis to store these hits & I was not able to tell the
schema as I don't know Redis. But again it is not the right way.
Question 2: web service -
cache - yes ---> return (timeout is 1 second)
else go to api call - yes ---> return (timeout 5 seconds)
else go to database - yes ---> return (timeout 10 seconds)
default error
You have to implement above kind of system where each module is used if it is Up, else check with next module.
What design pattern you will follow.
Question 3: Difference between SOAP & REST
Question 4: Have you used Micoservices?
Question 5: Which framework did you use in REST? He was suggesting like Jersey webserver, Spring.
Answer I gave : To this I said that I have used Jersey API, don't know about Jersey Webserver & I have used Springboot for
REST.
Question 1: You have a website & you want to know the number of hits made in last 5 seconds. Even a user refreshes the
page, it will be considered a new hit. What approach you will take for this?
Answer I gave : I will keep a file for each user having the timestamp of each hit made by that user. And when required, I will
check all the files to calculate the hits in last 5 seconds based on current timestamp. But it will be slower, so I
suggested later to use some in memory database like Redis to store these hits & I was not able to tell the
schema as I don't know Redis. But again it is not the right way.
Question 2: web service -
cache - yes ---> return (timeout is 1 second)
else go to api call - yes ---> return (timeout 5 seconds)
else go to database - yes ---> return (timeout 10 seconds)
default error
You have to implement above kind of system where each module is used if it is Up, else check with next module.
What design pattern you will follow.
Question 3: Difference between SOAP & REST
Question 4: Have you used Micoservices?
Question 5: Which framework did you use in REST? He was suggesting like Jersey webserver, Spring.
Answer I gave : To this I said that I have used Jersey API, don't know about Jersey Webserver & I have used Springboot for
REST.
Round 3 by Abhishek(Senior Manager):
This round was taken by some Senior Manager from Hot Wire in Expedia.
One question asked in this, which was also asked to me during Verizon interview & I never thought to look for it.
Now below I am giving one idea as per my understanding & it is just for your experiment purposes & don't try it in your production code -
public class CustomThreadPool {
private int size;
private BlockingQ bq;
private ArrayList<CustomThread> available;
private ArrayList<CustomThread> inUse;
private int num = 0;
private int count = 0;
private volatile States states;
private int waitInMS;
private int taskExecutionTime;
private int threadsCount;
private HashMap<String, Integer> tasksDone;
public CustomThreadPool(int size, int waitInMS, int taskExecutionTime) {
this.size = size;
bq = new BlockingQ(size);
available = new ArrayList<CustomThread>(size);
inUse = new ArrayList<CustomThread>(size);
states = new States();
this.waitInMS = waitInMS;
this.taskExecutionTime = taskExecutionTime;
threadsCount = size;
tasksDone = new HashMap<>();
}
public void submit(Object obj) {
CustomThread ct = null;
while(!bq.addTask(obj)) {
try {
Thread.sleep(taskExecutionTime/threadsCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if(size > 0 && (available.isEmpty() || (ct=available.get(0)) == null)) {
ct = new CustomThread(bq, "CustomThread"+count, available, inUse, states, waitInMS, tasksDone);
available.add(ct);
size--;
tasksDone.put("CustomThread"+count, 0);
ct.start();
count++;
}
num++;
}
public void done() {
while(true) {
if(bq.getListSize() == 0)
break;
}
states.setState(false);
System.out.println("Number of Tasks submitted : " + num);
System.out.println("Task Queue size when done method called : " + bq.getListSize());
System.out.println("Number of threads created : " + count);
tasksDone.forEach((a,b) -> System.out.println(a + ":" + b));
}
}
class BlockingQ {
private int size = 0;
private ArrayList list;
public BlockingQ(int size) {
list = new ArrayList(size);
this.size = size;
}
public int size() {
return size;
}
public boolean isEmpty() {
return list.isEmpty();
}
public boolean addTask(Object task) {
if(list.size() == size) {
// System.out.println("No space available.......");
return false;
}
// System.out.println("Added task : " + ((NitinThread)task).name);
return list.add(task);
}
public Object getTask() {
if(list.size() == 0) {
// System.out.println("No task available.......");
return null;
}
Object obj = null;
synchronized(this) {
if(list.size() > 0)
obj = list.remove(0);
}
return obj;
}
public int getListSize() {
return list.size();
}
}
class CustomThread extends Thread {
public boolean isAvailable = true;
private BlockingQ bq;
private String name;
private ArrayList<CustomThread> available;
private ArrayList<CustomThread> inUse;
private volatile States states;
private int waitInMS;
private HashMap<String, Integer> tasksDone;
CustomThread(BlockingQ bq, String name, ArrayList<CustomThread> available, ArrayList<CustomThread> inUse, States states, int waitInMS, HashMap<String, Integer> tasksDone) {
this.name = name;
this.bq = bq;
this.available = available;
this.inUse = inUse;
this.states = states;
this.waitInMS = waitInMS;
this.tasksDone = tasksDone;
}
@Override
public void run() {
while(states.isState()) {
// System.out.println(name + " running from CustomThreadPool....");
Object obj = bq.getTask();
if(obj == null) {
try {
Thread.sleep(waitInMS);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if(obj instanceof Runnable) {
isAvailable = false;
available.remove(this);
inUse.add(this);
tasksDone.put(name, tasksDone.get(name)+1);
// System.out.println(name + " running from CustomThreadPool with task " + ((NitinThread)obj).name);
((Runnable)obj).run();
isAvailable = true;
available.add(this);
inUse.remove(this);
}
}
}
}
class States {
private boolean state = true;
private boolean status;
public boolean isState() {
return state;
}
public void setState(boolean state) {
this.state = state;
}
public void updates() {
status = !status;
}
}
To test it below code I used & have attached results with different pool size -
This round was taken by some Senior Manager from Hot Wire in Expedia.
One question asked in this, which was also asked to me during Verizon interview & I never thought to look for it.
Now below I am giving one idea as per my understanding & it is just for your experiment purposes & don't try it in your production code -
public class CustomThreadPool {
private int size;
private BlockingQ bq;
private ArrayList<CustomThread> available;
private ArrayList<CustomThread> inUse;
private int num = 0;
private int count = 0;
private volatile States states;
private int waitInMS;
private int taskExecutionTime;
private int threadsCount;
private HashMap<String, Integer> tasksDone;
public CustomThreadPool(int size, int waitInMS, int taskExecutionTime) {
this.size = size;
bq = new BlockingQ(size);
available = new ArrayList<CustomThread>(size);
inUse = new ArrayList<CustomThread>(size);
states = new States();
this.waitInMS = waitInMS;
this.taskExecutionTime = taskExecutionTime;
threadsCount = size;
tasksDone = new HashMap<>();
}
public void submit(Object obj) {
CustomThread ct = null;
while(!bq.addTask(obj)) {
try {
Thread.sleep(taskExecutionTime/threadsCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if(size > 0 && (available.isEmpty() || (ct=available.get(0)) == null)) {
ct = new CustomThread(bq, "CustomThread"+count, available, inUse, states, waitInMS, tasksDone);
available.add(ct);
size--;
tasksDone.put("CustomThread"+count, 0);
ct.start();
count++;
}
num++;
}
public void done() {
while(true) {
if(bq.getListSize() == 0)
break;
}
states.setState(false);
System.out.println("Number of Tasks submitted : " + num);
System.out.println("Task Queue size when done method called : " + bq.getListSize());
System.out.println("Number of threads created : " + count);
tasksDone.forEach((a,b) -> System.out.println(a + ":" + b));
}
}
class BlockingQ {
private int size = 0;
private ArrayList list;
public BlockingQ(int size) {
list = new ArrayList(size);
this.size = size;
}
public int size() {
return size;
}
public boolean isEmpty() {
return list.isEmpty();
}
public boolean addTask(Object task) {
if(list.size() == size) {
// System.out.println("No space available.......");
return false;
}
// System.out.println("Added task : " + ((NitinThread)task).name);
return list.add(task);
}
public Object getTask() {
if(list.size() == 0) {
// System.out.println("No task available.......");
return null;
}
Object obj = null;
synchronized(this) {
if(list.size() > 0)
obj = list.remove(0);
}
return obj;
}
public int getListSize() {
return list.size();
}
}
class CustomThread extends Thread {
public boolean isAvailable = true;
private BlockingQ bq;
private String name;
private ArrayList<CustomThread> available;
private ArrayList<CustomThread> inUse;
private volatile States states;
private int waitInMS;
private HashMap<String, Integer> tasksDone;
CustomThread(BlockingQ bq, String name, ArrayList<CustomThread> available, ArrayList<CustomThread> inUse, States states, int waitInMS, HashMap<String, Integer> tasksDone) {
this.name = name;
this.bq = bq;
this.available = available;
this.inUse = inUse;
this.states = states;
this.waitInMS = waitInMS;
this.tasksDone = tasksDone;
}
@Override
public void run() {
while(states.isState()) {
// System.out.println(name + " running from CustomThreadPool....");
Object obj = bq.getTask();
if(obj == null) {
try {
Thread.sleep(waitInMS);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if(obj instanceof Runnable) {
isAvailable = false;
available.remove(this);
inUse.add(this);
tasksDone.put(name, tasksDone.get(name)+1);
// System.out.println(name + " running from CustomThreadPool with task " + ((NitinThread)obj).name);
((Runnable)obj).run();
isAvailable = true;
available.add(this);
inUse.remove(this);
}
}
}
}
class States {
private boolean state = true;
private boolean status;
public boolean isState() {
return state;
}
public void setState(boolean state) {
this.state = state;
}
public void updates() {
status = !status;
}
}
To test it below code I used & have attached results with different pool size -
Result of above for me as shown below. For you it can be bit different regarding number of threads being created.
But in short, it will not create more threads if threads are available to take that task.
Which I think can be better scenario.
Tweak the number of threads, time to wait, time to execute a thread & check the results.
Below first result is - When I asked for 1 thread pool.
Second result is - When I asked for 5 threads pool.
Third result is - When I asked for 15 threads pool.
But in short, it will not create more threads if threads are available to take that task.
Which I think can be better scenario.
Tweak the number of threads, time to wait, time to execute a thread & check the results.
Below first result is - When I asked for 1 thread pool.
Second result is - When I asked for 5 threads pool.
Third result is - When I asked for 15 threads pool.
