Snapdeal Interview Question for Senior Software Development Engineers


Country: India
Interview Type: In-Person




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

Since the data query is by date, my first instinct is to keep the data as a hash table keyed by date, and then keyed by city.
hash = {date: {city: temp}}

Getting the temp for a city on a particular date is in the avg case a O(1) hash lookup and another O(1) hash lookup in the city.

For finding the top 5, we would first get the data by date first. This will give us a unsorted list of {city: temp} value pairs. As we process the list, we can keep a list of top 5 values (min or max). If the new value is <//> of the min value, then we swap out fhe min value. This can be optimized by keeping this 5 array in sorted order.
Instead of doing any sorting on this array, since this is just a consta number, we can do a bubble of the value up until it is in the right place. e.g. the new number ifs first swapped with top_five[0] and then bubbled up until is it between top_filve[i], top_five[i+2] where top_five[i] < new_val < top_five[i+2]
So every new value can potentially result in a reordering of the top five list.

The complexity will be O(N * 1) where N is the number of cities. Worst case is
that the numbers are read in sorted order so that each data swaps out the old so it will process the top five. Best case is it will again O(N) where only the first 5 cities cause a swap out and after that no swap happens.

def preprocess(file, data):
    with open(file, 'r') as datafile:
        for line in datafile.readlines():
            (date, city, temp) = line.split()
            print 'Adding %s:%s to %s' % (city, temp, date)
            if date in data.keys():
                data[date][city] = temp
            else:
                data[date] = {city: temp}

def find_temp_city_date(date, city, data):
    try:
        return data[date][city]
    except KeyError:
        raise Exception("Date or City not in database")

def find_hottest_five(date, data):
    top_five = [(0, "") , (0, ""), (0, ""), (0, ""), (0, "")]
    for city, temp in data[date].items():
        if temp > top_five[0][0]:
            top_five[0] = (temp, city)
            for t in range(len(top_five) - 1):
                if top_five[t][0]  > top_five[t+1][0]:
                    (top_five[t], top_five[t+1]) = (top_five[t+1], top_five[t])
    print "%s" % top_five
    for d in reversed(top_five):
        print "(%s, %s)" % (d[0], d[1])

data = ('09-11-2015 Delhi 45\n'
        '09-11-2015 Guwahati 51\n'
        '09-11-2015 Kolkata 42\n'
        '09-11-2015 Bombay 35\n'
        '09-11-2015 Ahmedabad 35\n'
        '09-11-2015 Chandigarh 41\n'
        '09-11-2015 NewYork 25\n'
        '09-11-2015 SanFrancisco 40\n'
        '09-11-2015 Shanghai 23\n'
        '09-11-2015 Junea 20\n'
        '09-11-2015 Toronto 21\n'
        '10-11-2015 Delhi 45\n'
        '10-11-2015 Guwahati 51\n'
        '10-11-2015 Kolkata 42\n'
        '10-11-2015 Bombay 35\n'
        '10-11-2015 Ahmedabad 35\n'
        '10-11-2015 Chandigarh 40\n'
        '10-11-2015 NewYork 25\n'
        '10-11-2015 SanFrancisco 40\n'
        '10-11-2015 Shanghai 23\n'
        '10-11-2015 Junea 20\n'
        '11-11-2015 Toronto 21\n'
        '11-11-2015 Delhi 45\n'
        '11-11-2015 Guwahati 51\n'
        '11-11-2015 Kolkata 42\n'
        '11-11-2015 Bombay 35\n'
        '11-11-2015 Ahmedabad 35\n'
        '11-11-2015 Chandigarh 40\n'
        '11-11-2015 NewYork 25\n'
        '11-11-2015 SanFrancisco 40\n'
        '11-11-2015 Shanghai 23\n'
        '11-11-2015 Junea 20\n'
        '11-11-2015 Toronto 21\n')

with open("a.data", 'w') as f:
    f.write(data)

$ python city_temp.py
Adding Delhi:45 to 09-11-2015
Adding Guwahati:51 to 09-11-2015
Adding Kolkata:42 to 09-11-2015
Adding Bombay:35 to 09-11-2015
Adding Ahmedabad:35 to 09-11-2015
Adding Chandigarh:41 to 09-11-2015
Adding NewYork:25 to 09-11-2015
Adding SanFrancisco:40 to 09-11-2015
Adding Shanghai:23 to 09-11-2015
Adding Junea:20 to 09-11-2015
Adding Toronto:21 to 09-11-2015
Adding Delhi:45 to 10-11-2015
Adding Guwahati:51 to 10-11-2015
Adding Kolkata:42 to 10-11-2015
Adding Bombay:35 to 10-11-2015
Adding Ahmedabad:35 to 10-11-2015
Adding Chandigarh:40 to 10-11-2015
Adding NewYork:25 to 10-11-2015
Adding SanFrancisco:40 to 10-11-2015
Adding Shanghai:23 to 10-11-2015
Adding Junea:20 to 10-11-2015
Adding Toronto:21 to 11-11-2015
Adding Delhi:45 to 11-11-2015
Adding Guwahati:51 to 11-11-2015
Adding Kolkata:42 to 11-11-2015
Adding Bombay:35 to 11-11-2015
Adding Ahmedabad:35 to 11-11-2015
Adding Chandigarh:40 to 11-11-2015
Adding NewYork:25 to 11-11-2015
Adding SanFrancisco:40 to 11-11-2015
Adding Shanghai:23 to 11-11-2015
Adding Junea:20 to 11-11-2015
Adding Toronto:21 to 11-11-2015
[('40', 'SanFrancisco'), ('41', 'Chandigarh'), ('42', 'Kolkata'), ('45', 'Delhi'), ('51', 'Guwahati')]
(51, Guwahati)
(45, Delhi)
(42, Kolkata)
(41, Chandigarh)
(40, SanFrancisco)

- haroud December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it cannot be O(N).
It is O(N*logN), because when you get "an unsorted list", you should apply some sorting algorithm. The fastest sorting algorithms (merge sort, etc.) have complexity O(N*logN) in average and worst cases.
Of course, N is the number of cities in the database.

- zr.roman December 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I stated O(N) because I am considering 5 to a constant. I do not sort the whole list but for every city, I will do at most 5 operations to place it in the sorted list of top 5.

- haroud December 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is assuming that all the dates are in order like the example and all dates are there (no gaps).

Read the first and last lines of each file. There are you have a range of all dates. Take the total number of days in divide the total file size by the total number of days this will give you the position to set the pointer at for a particular date.

Also assuming that we have the same number of cities for each date, take that particular date block with each city's name and store it in a we array.

To get a temperature for particular city do a binary search found the city name and get the temperature.

To get the the average of the top five cities do up merge sort sort by temperature lowest to highest get the top five indexes and take the average of that.

O (log n) solution

- TheShocker1999 December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Hash3Columns {

    using CustomHashTable = Dictionary<System.DateTime, Dictionary<string, int>>;

    class Program {

        static CustomHashTable _database = new CustomHashTable();

        private static string GetTemperature( string city, DateTime date ) {
            try {
                return _database[ date ][ city ].ToString();
            }
            catch (KeyNotFoundException) {
                return "No data in database";
            }
        }
        
        private static string[] GetHottestCities( DateTime date, int n ) {
            return _database[ date ]
                    .OrderByDescending( x => x.Value )
                    .Take( n )
                    .Select( y => y.Key )
                    .ToArray();
        }

        private static string[] GetColdestCities( DateTime date, int n ) {
            return _database[ date ]
                    .OrderBy( x => x.Value )
                    .Take( n )
                    .Select( y => y.Key )
                    .ToArray();
        }

        static void Main(string[] args)
        {
            // code for testing here
        }
    }
}

- zr.roman December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use map reduce

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

Create a City implementing Comparable interface

public class City implements Comparable<City>{

String name;
String date;
String temp;

public City(String name, String date, String temp) {
// TODO Auto-generated constructor stub
this.name = name;
this.date = date;
this.temp = temp;
}

@Override
public int compareTo(City o) {
if(Integer.parseInt(this.temp)<Integer.parseInt(o.temp))
return 1;
else if(Integer.parseInt(this.temp)>Integer.parseInt(o.temp))
return -1;
else
return 0;
}



}

Then Create a City Map Builder Class as given below and write methods:::



public class CityBuilder {

List<City> cities;
Map<String, List<City>> map = new HashMap<String, List<City>>();

public CityBuilder(List<City> cities) {
// TODO Auto-generated constructor stub
this.cities = cities;
map = cityTemperatureMap(cities);
}

public List<City> listCities(BufferedReader br) throws IOException{

List<City> result = new ArrayList<City>();
while(br.readLine()!=null){

StringTokenizer str = new StringTokenizer(br.readLine());
City city = new City(str.nextToken(), str.nextToken(), str.nextToken());
result.add(city);
}


return result;
}

public Map<String, List<City>> cityTemperatureMap(List<City> list){

for(City city:list){

boolean b = map.containsKey(city.date);
if(b==true){

List<City> result = map.get(city.date);
result.add(city);
map.put(city.date, result);

}else{

List<City> resul = new ArrayList<City>();
resul.add(city);
map.put(city.date, resul);

}

}

return map;

}

public List<City> listForADate(String date){

return map.get(date);

}

public int getTemperature(String name, String date){

List<City> list = map.get(date);
for(City c:list){

if(c.name.equals(name)){
return Integer.parseInt(c.temp);
}

}

return -1;
}

}

- Siddhahast April 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a City implementing Comparable interface

public class City implements Comparable<City>{

String name;
String date;
String temp;

public City(String name, String date, String temp) {
// TODO Auto-generated constructor stub
this.name = name;
this.date = date;
this.temp = temp;
}

@Override
public int compareTo(City o) {
if(Integer.parseInt(this.temp)<Integer.parseInt(o.temp))
return 1;
else if(Integer.parseInt(this.temp)>Integer.parseInt(o.temp))
return -1;
else
return 0;
}



}

Then Create a City Map Builder Class as given below and write methods:::



public class CityBuilder {

List<City> cities;
Map<String, List<City>> map = new HashMap<String, List<City>>();

public CityBuilder(List<City> cities) {
// TODO Auto-generated constructor stub
this.cities = cities;
map = cityTemperatureMap(cities);
}

public List<City> listCities(BufferedReader br) throws IOException{

List<City> result = new ArrayList<City>();
while(br.readLine()!=null){

StringTokenizer str = new StringTokenizer(br.readLine());
City city = new City(str.nextToken(), str.nextToken(), str.nextToken());
result.add(city);
}


return result;
}

public Map<String, List<City>> cityTemperatureMap(List<City> list){

for(City city:list){

boolean b = map.containsKey(city.date);
if(b==true){

List<City> result = map.get(city.date);
result.add(city);
map.put(city.date, result);

}else{

List<City> resul = new ArrayList<City>();
resul.add(city);
map.put(city.date, resul);

}

}

return map;

}

public List<City> listForADate(String date){

return map.get(date);

}

public int getTemperature(String name, String date){

List<City> list = map.get(date);
for(City c:list){

if(c.name.equals(name)){
return Integer.parseInt(c.temp);
}

}

return -1;
}

}

- Siddhahast April 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use HashMap to store date.toString as key, So we can have fast lookup based on date.
instead of storing (city,temp) pair in hashmap use treesort / double end dequeue / priority queue. Now insert will be done in O(c + nlogn), both queries will be address in O(c + n)

- nilesh bhosale October 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If the cities are set list for example of Darla only 50 cities. You you could read the first line of the fall and the last line of the file it will give you a range of dates. Take this range and get a number of days and you can take you take the total file size divided by the number of days. These calculations you could get each date group by block.

Place the block into an array and do a merge sort on the array this will give you an index of each cities position for future searches. Get date block plus cities index to get each cities temperature for that day if cities appear in same order in each date block. If not search for city name using binary search on each block.

For each temperature you that the date block, merge sort by lowest temperature and then get the top five indexes and then get an average of that.

O (log n) running time.

- Anonymous December 01, 2015 | 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