Booking.com Interview Question for Software Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

@Steephen...I just bwanted to ask why you have used an arraylist for implementing the queue?Shouldnt we use a linkedlist instead ?As in case of linkedlist we only need to change the pointers but in arraylist each item will have to be shifted by one position ?

- prashant.tah September 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public void solve(String[] input, String word, int k) {

    List<String> cappedList = new ArrayList<String>(k) {
      @Override
      public boolean add(String s) {
        if (size() > k) {
          super.remove(0);
        }
        return super.add(s);
      }
    };

    for(String s : input) {
      cappedList.add(s);
      if (s.equals(word)) {
        break;
      }
    }
    cappedList.stream().forEach(System.out::println);
  }

- capped list January 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a map<word, index> and sequence of words (typically an array). Map is either backed by hashing or BST. Now by word index is found if exists then from original word sequence expected output is obtained.

Assumed this whole operation can be done using in memory. If not then it may need external indexing.

- Anonymous September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

From file create a map<word, index> which is backed by hashing, BST etc and original word sequences, typically by an array. Now given word index if found if exists then from original word sequences expected output can be obtained.

Assumed memory is fit for all words, if not then it may need external indexing etc.

- Debasis Jana September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

From file create a map<word, index> which is backed by hashing, BST etc and original word sequences, typically by an array. Now given word index if found if exists then from original word sequences expected output can be obtained.

Assumed memory is fit for all words, if not then it may need external indexing etc.

- debasis.jana.iit September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@prashant.tah why is time complexity of your solution O(nm) ? Is it not O(n) ?
You have a queue of size k+1. If the last word entering the queue was w then you drain and print the queue. Also, there is no mention of whether any words are repeated in the file.

- Makarand September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think your solution idea is good. But it's a simple question. So, what was the interviewer interested in?
- the algorithm runs in O(n), and most time is consumed by fetching data from disc to memory.
- the queue contributes to memory usage and constant time factors. A ringbuffer could help on reducing constant factors on time and space complexity, (less copying around) but this optimization will come for the price of code complexity, so it needs to be well decided.

Other than that, I only see he was thinking of a pattern instead a word to look for, which would explain your O(n*m) time. In this case, preprocess the pattern so matching is O(n) again.

- Chris September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.home.careercup;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
This is NOT a solution  with space complexity lesser than O(n)
I am watching to see if anyone posts a solution that is better than O(n) space
All solutions that use a map <word, index> already take up O(n) space inside
the index. Correct me if I am wrong.
*/
public class KGrepp {
    final static String[] words = {"aaa", "bbb", "ccc", "booking", "alpha", "beta", "gamma"};
    private static Map<String, List<Long>> wordLocator = new HashMap<>();

    static {
        build(words);
    }

    public static void main(String[] args) {
        grep("beta", 2);
        System.out.println("===");
        grep("booking", 3);
    }

    static void build(String[] words) {
        for (int i = 0; i < words.length; i++) {
            final String w = words[i];
            wordLocator.putIfAbsent(w, new ArrayList<>(2));
            wordLocator.get(w).add((long) i);
        }
    }

    static void grep(String w, int k) {
        if (k > words.length - 1) return;
        List<Long> locations = wordLocator.get(w);
        if (locations == null || locations.size() == 0) return;
        for (long loc : locations) {
            for (long i = Math.max(0, loc - k); i <= loc; i++) {
                System.out.println(words[(int) i]);
            }
        }
    }
}

- Makarand September 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I assume it can be achieved in O(n) complexity. We don't need to buffer the data and search for the key string again within buffer. Instead keep only k number of lines in memory and if new line is equals to key string, print the buffer along with key.

I assume, k number of lines are read already before reading the key value.

package careercup;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class LimitedLengthQueue {

    private List<String> innerStore;
    private int size;
    private static final String FILENAME="C:/filepath.txt.txt";
    public LimitedLengthQueue(int size) {
        this.innerStore = new ArrayList<>();
        this.size = size;
    }

    boolean add(String s){
        if(innerStore.size() == size){
            innerStore.remove(0);
            innerStore.add(s);
            return true;
        }
        innerStore.add(s);
        return true;
    }


    public static void main(String[] args)
                     throws FileNotFoundException, IOException  {
        LimitedLengthQueue inputQueue =
                   new LimitedLengthQueue(Integer.parseInt(args[0]));
        String key = args[1];

        try( FileReader fr = new FileReader(FILENAME);
             BufferedReader br = new BufferedReader(fr)){

            String input = null;

            while( (input = br.readLine()) != null){

                if(key.equals(input.trim())){
                    inputQueue.innerStore.forEach(System.out::println);
                    System.out.println(input);
                    break;
                }
                inputQueue.add(input);
             }
        }
    }
}

- steephen September 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Chris,

Wouldnt the time complxity be O(n*m) as for each iteration there will be m comparisons to check whether the iterated word is matching with the given word w?

Also can you please explain prepocessing thing in a little detail or give me a reference where i can read this up? can this help in bringing down space/time complexity?

- prashant.tah September 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@makarand
time complxity be O(n*m) as for each iteration there will be m comparisons to check whether the iterated word is matching with the given word w?Is this the right direction of thinking?

- prashant.tah September 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@prashant.tah Thanks for clarifying that up. String comparison is O(m) where m is word width in the worst case. You are right in saying that the order is O(nm)

- Makarand September 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@prashant.tah
maybe imagine it that way:
- if you extract the words from the input buffer and then compare each extracted word against w, what do you do:
- extract approximately n/m words in O(n)
- after (or while) doing that you do for each word at most m comparsions, which is again O(n)
- total of O(n)

or another way:
- while finding word separators in the input buffer, you could compare against w, knowing if w
is a match while you extract. This is O(n), too - slightly more obvious.

But if you try to search a pattern within each extracted word with a naive approach you would do:
- extracting n/m words in O(n)
- for each word of length m and the pattern of length p, perform p*(m-p+1) comparisons.

For pattern matching in linear time Knuth-Morris-Pratt is especially interesting because it covers the whole prefix and suffix discussion which I think gives some insight (a pattern is a match if it has a common prefix on a common suffix - sounds strange until it makes click).

- Chris September 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the worst case we can assume that each word in the file is of length m and the pattern is also of length m and the mismatch occurs in the last character of each word so the O(n*m)

Also can you please explain the n/m thing that you wrote..i dint get it

- prashant.tah September 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@prashant.tah: oh, I see, n is the number of words, I assumed n is the length of the input stream - but question states number of words - my mistake.
In this case it's of course O(n*m). That explains both the O(n*m) and n/m number of words.

- Chris September 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

binary search in the file, one index starts at position 0, another one starts in position N. When the word is found, you just move up or down that position and return those values ;)

This solution is O(n/2)

- carovaldezg November 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Push k words into a queue.
2. Read the rest of the file word by word. Push the word onto the queue, then pop one off. The queue will always be size k. If the word that just got pushed is w, return the queue and break out of reading the file.

- andreaowu January 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we use a balanced binary tree to represent the document, where each node contains the word and the line or offset where we found the word in the document, we can have time complexity of log(n) for lookup.

Then we have to find the k words previous.

We keep the original ArrayList and get the k words using index O(1) each operation thus O(k).

Time complexity is O(k*log(n)) for lookup
Space complexity is O(2*n)

Pros: very fast
Cons: maintenance, code complexity

- Anonymous June 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a circular link list of size k and update the nodes in the circular fashion when the current word not matched to the searched word. If word matched print all k elements from the link list.

- rinku August 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void grep(String[] input, String word, int k) {

List<String> cappedList = new ArrayList<String>(k) {
@Override
public boolean add(String s) {
if (size() > k) {
super.remove(0);
}
return super.add(s);
}
};

for(String s : input) {
cappedList.add(s);
if (s.equals(word)) {
break;
}
}
cappedList.stream().forEach(System.out::println);
}

- Anonymous January 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void solve(String[] input, String word, int k) {

    List<String> cappedList = new ArrayList<String>(k) {
      @Override
      public boolean add(String s) {
        if (size() > k) {
          super.remove(0);
        }
        return super.add(s);
      }
    };

    for(String s : input) {
      cappedList.add(s);
      if (s.equals(word)) {
        break;
      }
    }
    cappedList.stream().forEach(System.out::println);
  }

- Anonymous January 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void solve(String[] input, String word, int k) {

    List<String> cappedList = new ArrayList<String>(k) {
      @Override
      public boolean add(String s) {
        if (size() > k) {
          super.remove(0);
        }
        return super.add(s);
      }
    };

    for(String s : input) {
      cappedList.add(s);
      if (s.equals(word)) {
        break;
      }
    }
    cappedList.stream().forEach(System.out::println);
  }

- Anonymous January 12, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More